It might not be a quick fix, but spinning off older entries into their own quasi-archive tables could help, especially if they're ones that are rarely accessed. You'd need a routing mechanism somewhere to detect when to jump from the main table to the archives.
And do you have something like Redis in place for caching common / recent queries? That could help for material that's frequently accessed but doesn't change often.