[ainsej]

Caching is definitely a must have, both an external cache (Memcache, Redis) and tuning MySQL's own caches in the configuration, using InnoDB and MySQL means you can configure a large buffer in the MySQL config to speed things up considerably

Disk speed could also be a huge issue, especially on a VPS where resources are shared between many virtual machines, consider migrating your database off to a dedicated server (Preferably one with an SSD), depending on where you are in the world OVH might be a good choice.