Ключ хоста SSH неожиданно меняется

Я выкатил новый /etc/ssh/sshd_config с Puppet на тестовом сервере Ubuntu 12.04. Конфиг был точно таким же, как и предыдущий, за исключением того, что была удалена следующая строка:

HostKey /etc/ssh/ssh_host_ecdsa_key

Я заметил, что получаю много похожих, но меняющихся ошибок при попытке подключения к коробке, начинающейся тогда, например: "Ключ хоста RSA для %hostname% изменился, а ключ для соответствующего IP-адреса %ipaddress% не изменился."

Я предположил, что это потому, что мой компьютер ранее использовал ключ ECDSA по умолчанию, и это было сейчас недоступно. Поэтому я добавил эту строку обратно sshd_config и перезапустил SSH.

Это не решило проблему полностью, и с тех пор я сталкиваюсь с постоянными проблемами. Я смогу нормально подключиться к серверу несколько раз, может, даже несколько дней подряд. Затем внезапно я получаю ошибки, что ключ хоста изменился, и сервер перестает принимать мой открытый ключ для аутентификации.

Всегда кажется, что, как только я немного поиграюсь с ним и подключусь из другого места, я внезапно смогу снова подключиться к своему открытому ключу, и у меня больше не будет ошибки о возможном человеке в середине атака.

Я попытался восстановить все 3 ключа хоста несколько дней назад (удалил их и запустил dpkg-reconfigure openssh-server который их возродил). Как и ожидалось, мне пришлось удалить старые ключи и принять новые, прежде чем я смог подключиться. Я думал, может быть, это было исправлено тогда, но проблема теперь вернулась.

Ничто не изменило ни один из ключей хоста в /etc/ssh/ с тех пор, как я обновил их в последний раз - так что может привести к тому, что я часто не смогу подключиться, если мой открытый ключ не будет работать, а затем в конце концов примет новый ключ и снова все начнет работать нормально?

Когда что-то не работает (когда я получаю ошибку об изменении ключа хоста, а затем сервер перестает принимать мой открытый ключ), на сервер ничего не записывается /var/log/auth.log, Это заставляет меня думать, что, может быть, иногда это происходит с другой машиной, но я не знаю, как это возможно, поскольку запись DNS верна и всегда возвращает один и тот же IP-адрес.