Да, я немного вникла - оказывается это как стандартная клубника - без соусов ни запаха, ни вкуса, один вид только - нужно всякие ускорители, кэшители... - что ж, отложим эту задачу на потом - хотя, наверное, где-то есть в Сети готовый пошаговый мануал - "Вы купили ВПС? Не радуйтесь!" - покупайте пиво, конфеты и начинайте настраивать все...

Начните с вопроса: зачем вы арендовали vps.

Разумеется для vps требуется кто-то, кто будет необходимое окружение настраивать. И более того, нужен кто-то, кто будет за этим следить в дальнейшем. В этом смысл VPS и заключается. Вы получаете root и настраиваете сами (или через вашего администратора) то что вам необходимо и так, как вам необходимо.
Если у вас нет потребности настроить систему - то зачем вам VPS? Ищите какой-нибудь PaaS или shared hosting. Там стоимость услуг системного администрирования включена в прайс.

Как все - скрипты мои на хостинге выходили за лимиты - расширить лимиты = купить ВПС

Тогда следующий вопрос: чем не устраивает 8сек? Может с этим можно жить и не замечать разницы?
(Добавление)
Ну...вдруг
(Добавление)
И думаю тут подкруткой кэшеров не обойтись. Раз идет парсинг регулярками как основная нагрузка, то явно проц проседает. Гляди top.
И как выше говорили на хостинге на толпу мощный проц. А у тебя на виртуалке его кусочек выделен.