Почему не получается зайти на сервер по SSH?

Всем привет!
Есть 2 виртуальных сервера с ОС Ubuntu. На каждый из них был настроен доступ по shh через root без пароля.
Все работало хорошо, но неожиданно перестала работать авторизация без пароля по ключу. При попытке авторизации вижу сообщение "Server refused public-key signature despite accepting key!" . И так на обоих серверах.
Установил в конфиге shh logging DEBUG и в auth.log вижу :

Nov 1 06:05:10 sshd[10270]: debug1: userauth-request for user root service ssh-connection method none [preauth]
Nov 1 06:05:10 sshd[10270]: debug1: attempt 0 failures 0 [preauth]
Nov 1 06:05:10 sshd[10270]: debug1: PAM: initializing for "root"
Nov 1 06:05:10 sshd[10270]: debug1: PAM: setting PAM_RHOST to
Nov 1 06:05:10 sshd[10270]: debug1: PAM: setting PAM_TTY to "ssh"
Nov 1 06:05:10 sshd[10270]: debug1: userauth-request for user root service ssh-connection method publickey [preauth]
Nov 1 06:05:10 sshd[10270]: debug1: attempt 1 failures 0 [preauth]
Nov 1 06:05:10 sshd[10270]: debug1: test whether pkalg/pkblob are acceptable [preauth]
Nov 1 06:05:10 sshd[10270]: debug1: temporarily_use_uid: 0/0 (e=0/0)
Nov 1 06:05:10 sshd[10270]: debug1: trying public key file /root/.ssh/authorized_keys
Nov 1 06:05:10 sshd[10270]: debug1: fd 4 clearing O_NONBLOCK
Nov 1 06:05:10 sshd[10270]: debug1: matching key found: file /root/.ssh/authorized_keys, line 5 RSA
Nov 1 06:05:10 sshd[10270]: debug1: restore_uid: 0/0
Nov 1 06:05:10 sshd[10270]: Postponed publickey for root from 000.000.000.251 port 17033 ssh2 [preauth]
Nov 1 06:05:10 sshd[10270]: debug1: userauth-request for user root service ssh-connection method publickey [preauth]
Nov 1 06:05:10 sshd[10270]: debug1: attempt 2 failures 0 [preauth]
Nov 1 06:05:10 sshd[10270]: debug1: temporarily_use_uid: 0/0 (e=0/0)
Nov 1 06:05:10 sshd[10270]: debug1: trying public key file /root/.ssh/authorized_keys
Nov 1 06:05:10 sshd[10270]: debug1: fd 4 clearing O_NONBLOCK
Nov 1 06:05:10 sshd[10270]: debug1: matching key found: file /root/.ssh/authorized_keys, line 5 RSA
Nov 1 06:05:10 sshd[10270]: debug1: restore_uid: 0/0
Nov 1 06:05:10 sshd[10270]: error: hash mismatch
Nov 1 06:05:10 sshd[10270]: debug1: ssh_rsa_verify: signature incorrect
Nov 1 06:05:10 sshd[10270]: Failed publickey for root from 000.000.000.000 port 17033

Пробовал генерировать новые ключи и добавлять в auth_keys, изменять права на .shh и на auth_keys.
Ошибка остается прежней.

Соединяюсь с ПК на винде через putty.