Столкнулся с интересным поведением SSH. При попытке авторизоваться на Linux сервере из винды через PuTTY я получил ошибку «Server refused our key». Причём из под линукса с этим же ключом всё заходит отлично. В логах появляется такая строка:

userauth_pubkey: key type ssh-rsa not in PubkeyAcceptedAlgorithms [preauth]

Как оказалось, с версии openssh 8.8 (предположительно) что-то изменилось в алгоритмах шифрования.

Есть два решения этой проблемы:

1. Обновить PuTTY до последней версии

Просто скачиваем с официального сайта дистрибутив с последней версией и запускаем. Всё сразу должно заработать. Мне это и помогло. Аналогично поступил и с другими программами, которые работают с ключами: WinSCP, KeePass, и его плагин KeeAgent.

2. Перейти на алгоритм ECDSA

Если по каким-то причинам вы не можете обновить используемое ПО, то можно перейти на использование алгоритма ECDSA для генерации ключей. В этом случае вам конечно же придётся создать новую пару ключей.

В PuTTYGen это делается просто выбором соответствующего переключателя:

В Linux это делается с помощью команды:

# ssh-keygen -t ecdsa