Почему перестало работать подключение через PuTTY?

Сам не сталкивался, если честно, но на форуме нашел такое решение проблемы - нужно добавить в /etc/ssh/sshd_config следующую строчку:

KexAlgorithms curve25519-sha256@libssh.org,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group14-sha1,diffie-hellman-group-exchange-sha1,diffie-hellman-group1-sha1

Пробовали?

Там достаточно внятно написано:
"did not find one of algos diffie-hellman-group1-sha1 in list "
Значит, в настройках соединений SSH на клиенте или сервере были установлены какие-то ограничения по типам алгоритмов шифрования, которые можно использовать.
Скорее всего, это сделали Вы сами на PuTTY, вспоминайте. Сделайте в PuTTY новое соединение к серверу с дефолтными настройками.
P.S. Я не служба поддержки.