Смотри что выполняется в базе show processlist, в идеале профилируй все запросы, смотри какие больше всего времени выполняются, сделать это можно как на стороне приложения (бакэнда), особенно если используется какая то прослойка для базы данных, так и средствами базы данных, гугли
mysql slow query log (на самом деле там куча способов проанализировать работу но чаще удобнее это делать со стороны бакэнда)
Проанализируй самые тормозные запросы, вполне возможно неправильно индексы настроены и таблицы читаются full scan (перестали влезать в кеш).
С некоторой вероятностью - размер базы дошел до некоторого критического, и индексы перестали влезать в оперативную память, но сами запросы к диску все еще кешируются ОС (причем не гостевой а хост системы)
Ну и нельзя исключать злонамеренные действия хостера, особенно дешевые реселеры любят понижать скорость работы VPS-ок с целью вынудить перейти на более дорогие тарифы.