Os servidores costumam ter uma chave de host por algoritmo (/etc/ssh/ssh_host_ed25519_key, …_ecdsa_key, …_rsa_key), e a ordem de HostKeyAlgorithms do cliente decide qual delas é usada. No primeiro contato, o OpenSSH mostra a impressão digital SHA-256 e pergunta se deve confiar nela; depois disso, uma mudança gera WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! e a conexão é interrompida (com StrictHostKeyChecking no valor padrão).
Rotação de chaves de host sem quebrar os clientes: o UpdateHostKeys do OpenSSH (ativado por padrão nos clientes recentes) permite que o servidor anuncie todas as suas chaves de host depois da autenticação, para que os clientes aprendam as novas antes de a antiga ser removida. Frotas de servidores evitam totalmente a confiança no primeiro uso com certificados de host (@cert-authority no known_hosts) ou com registros SSHFP assinados com DNSSEC (RFC 4255).
Imagens base (golden images) que já trazem as chaves de host embutidas dão a mesma identidade a todo servidor clonado; gere as chaves de novo na primeira inicialização. O HashKnownHosts armazena os nomes de host como hashes, para que um arquivo known_hosts roubado não revele a lista dos seus servidores.