Проблема решена:
1. Долгая авторизация по SSH и невозможность пользоваться Интернетом с сервера решилась заменой DNS провайдера, оказалось DNS не рабочие.
2. Поменял формат логов Apache, т.к. выяснилось, что Apache даже с нормальными DNS тем не менее не может резолвить имена. Поставил чтобы писал в логи только IP адреса клиентов и тем самым скорость работы вернулась к прежней, даже стало работать чуть быстрее. Такие логи меня устраивают более чем, тем более что никогда не поздно преобразовать ip в имена посредством утилиты logresolve.
В целом проблема оказалась на стороне провайдера. О своих приключения отписался в службу поддержки, посмотрим что они решат. Замечу что ничего подобного никогда не наблюдалось у Amazon. Почему всегда такое происходит с русскими компаниями, остается открытым вопросом.