Какие характеристики vps (сколько ядер, какая частота процессора, сколько ОЗУ, какой тип памяти используется, SSD или HDD диск)?
Какая средняя нагрузка на впс? Какие процессы в топе top?
Самый простой способ проверить, что проблема не в phpmyadmin, как сказали выше, сделать аналогичный запрос через консоль.
Если проблема в phpmyadmin, то рекомендую посмотреть в сторону adminer. Он проще и более легковесный.
Если проблема не в phpmyadmin, то нужно бороться с причинами проблемы (нагрузка на процессор, забитая память, диск и прочее)