Server haben in der Regel einen Hostschlüssel pro Algorithmus (/etc/ssh/ssh_host_ed25519_key, …_ecdsa_key, …_rsa_key), und die Reihenfolge in HostKeyAlgorithms des Clients entscheidet, welcher verwendet wird. Beim ersten Kontakt zeigt OpenSSH den SHA-256-Fingerabdruck und fragt, ob du ihm vertraust; danach führt eine Änderung zur Warnung WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!, und die Verbindung bricht ab (wenn StrictHostKeyChecking auf dem Standardwert steht).
Hostschlüssel rotieren, ohne dass Verbindungen von Clients scheitern: Mit UpdateHostKeys von OpenSSH (in aktuellen Clients standardmäßig aktiv) kündigt ein Server nach der Authentifizierung alle seine Hostschlüssel an, sodass Clients neue kennenlernen, bevor der alte entfernt wird. Serverflotten verzichten mit Host-Zertifikaten (@cert-authority in known_hosts) oder per DNSSEC signierten SSHFP-Einträgen (RFC 4255) ganz auf das Vertrauen beim ersten Kontakt.
Golden Images mit eingebauten Hostschlüsseln geben jedem geklonten Server dieselbe Identität; erzeuge die Schlüssel beim ersten Start neu. HashKnownHosts speichert Hostnamen als Hashes, sodass eine gestohlene Datei known_hosts deine Server nicht auflistet.