Я бы сказал, что, скорее всего, ваша база данных связана с IO, я точно не знаю, что такое «VPS», но если это какая-то виртуальная машина, то почти гарантированно будет очень плохо выполнять IO.
Получите это на реальном оборудовании как можно скорее; и получите разумное количество баранов (1G крошечный; 16G звучит более разумно).
Тогда вы сможете настроить свою БД, чтобы она могла вести себя правильно. Насколько велики ваши данные? Если вы можете заставить их всех (или большинство из них) поместиться в кеше вашей базы данных (не в каверзном кеше запросов, а в пуле буферов innodb), тогда сделайте это.
Я предполагаю, что вы используете движок innodb; если это так, то настройте буферный пул так, чтобы он был достаточно большим для всех ваших данных - если вам не хватает оперативной памяти, покупайте больше, пока не сделаете (Нет, правда!).
Тогда ваши запросы к БД должны быть быстрыми, даже если они довольно плохие (да).
Сложность в том, что, если у вас есть одна машина, как разделить использование оперативной памяти между mysql и PHP - веб-сервер (я полагаю, Apache), особенно если вы используете prefork и большое количество MaxClients, может использовать до баран и лишить его вашей базы данных.
Получите достойный мониторинг на работе (с трендами), тщательно внесите изменения и запишите точно, когда вы их сделали.