Sei que essa é uma pergunta antiga, mas acho que essa é uma adição válida para pesquisas futuras.
Atualizar seu sshd não deve fazer com que a chave do host seja recriada, então você está bem com uma atualização.
A atualização do seu servidor, no entanto, pode causar a criação de uma nova chave de host. A mensagem que você está descrevendo aparece quando o cliente ssh não reconhece a chave do host do servidor, portanto, qualquer coisa que altere a chave do host causará esse problema.
Uma maneira de contornar isso é remodelar o uso do ssh para usar certificados em vez de senhas e chaves.
Enquanto isso leva algum trabalho, e um pouco de remodelação, mas vale a pena você querer assinar melhor seus servidores.
Existe um guia muito bom aqui:
link
Basicamente, o que você faz é criar uma CA para os servidores e uma CA para os usuários e usá-los para autenticar os clientes e servidores respectivamente.
Você ainda veria a mensagem acima se tiver feito login com nome de usuário / senha, mas para qualquer um que fizer login com certificados, a única coisa que importa é que o certificado de host do servidor seja assinado pela CA do servidor.