It's a dozen tables or so, right? Let's see the result of EXPLAIN EXTENDED on the whole query, along with SHOW CREATE TABLE for each referenced table.
> The time takes has increased considerably through the last month, way more than the amount of data. 30 days ago the query took 20seconds, now it takes 50 seconds. Apparently there are no changes to mysql configuration, so what could this be? (Im on a virtual private server).
You could be running into software bottlenecks. How much RAM is there, what is innodb_buffer_pool_size? Review
http://mysql.rjweb.org/doc.php/memory, experiment with changes (with query caching turned off).
Two famous workarounds if all else fails: (i) maintain reporting tables representing results of the skowest subqueries, (ii) guarantee it's in the user's cache by always executing this query in the background when a user who is likely to execute it first logs in.