Проблема c настройками SSH после взлома сервера. Как можно изменить поведение сервера и клиента без изменения ssh_config и sshd_config ?

Краткая предыстория для понимания ситуации.

Наш убунту-сервер взломали буквально на следующий день после скандала с уязвимостью Shellshock. Не знаю применили конкретно её или нашли какую-то другую дыру, но к нам c одного румынского IP-адреса проник злоумышленник. Раньше я в душе посмеивался над ихними ботами из ZmEu, которые пытались запустить несуществующий у меня phpMyAdmin, а тут вдруг на мой сервер пошли жалобы на предмет аналогичного брутфорса.

Когда я подключился, хакер еще висел в системе (или недавно перезашел) под пользователем root. Я его кильнул и начал наводить порядки. Незваный гость особо себя не ограничивал - установил и запустил программное обеспечение для узла ботнета (сканеры и IRC-сервер), раскидал свои ключи SSH под пользователями, переписал мне таблицу iptables и постирал логи предыдущих действий. Таким образом я точно не знаю, что он успел наделать кроме самих последних команд перед его килом из системы...

Текущая проблема.

Чужой код и левые SSH-ключики почистил, правила фаервола востановил, почти всех пользователей заблокировал, а оставшимся сменил пароли. Но при последующем использовании сервера обнаружил ряд нестыковок.

Для начала, при попытке по SSH зайти моего сервера на комп из видимой ему локалки, я получил предупреждение о неизвестном хосте. Проверил в ~/.ssh/known_hosts - его запись там была (я больше никуда собственно и не хожу с данного сервера) с указанием шифрования ecdsa-sha2-nistp256. Я подтвердил вход на сервер и получил в файле известных хостов вторую запись с типом шифрования ssh-rsa. Более того, теперь при заходах на локальный компьютер я все время получаю сообщение:
/etc/ssh/ssh_config line 52: Unsupported option "GSSAPIAuthentication"
/etc/ssh/ssh_config line 53: Unsupported option "GSSAPIDelegateCredentials"

Т.е. поведение локального ssh-клиента изменилось: и теперь он вместо привычного SHA-2 стал почему-то использовать SHA-1.

Еще. Я в терминале работаю в основном под MC. Вместо привычной псевдографики я теперь вижу рисование крякозябами. Помогла только смена кодировки в putty с UTF-8 на KOI8-R (если делать подключение на вышеупомянутый комп из локалки, то там все в порядке и мне приходится делать обратную смену с KOI8-R на UTF-8 чтобы снова видеть нормальный MC).

Как злоумышленник провернул все эти фокусы? Как я уже упомянул ранее, файлы ssh_config и sshd_config из директории /etc/ssh не изменились. Но даже, если предположить, что с помощью touch даты вернули назад на 2012 год, то в sshd_config все равно явно указано использование протокола 2. И прочие настройки визуально никак не изменены. Поиск по файловой системе показал, что это единственные экземпляры конфигов и других (пользовательских) нет.

Второстепенная проблема но тоже связана с SSH.

Когда пошли тревожные звоночки, я был в гостях. Там же с чужого компа я несколько раз подключался по putty не по ключу, а с явным указанием логина и пароля. Потом при анализе последних измененных в файловой системе я наткнулся на очень неприятный файлик /etc/ppp/.ilog , в котором в текстовом виде был прописан мой логин и пароль в количестве раз, сколько я подключался без ключа. Время модификации файла совпадало со временем моего последнего входа по SSH. Но что самое паскудное - мой последний вход был уже после проведения "лечебных" процедур и последующего ребута сервера. Поэтому возможно что вторая проблема и первая имеют общую причину.

Поскольку я уже упомянул про ребут и оставшиеся проблемы, то хочу сразу отметить, что я уже проверил кронтабы пользователей и содержимое директорий /etc/rcX.d и ничего нового/необычного не обнаружил.

Моя фантазия выдохлась... Прошу подсказок от "знатоков" и более опытных коллег.