Обычно у сервера есть по одному ключу хоста на каждый алгоритм (/etc/ssh/ssh_host_ed25519_key, …_ecdsa_key, …_rsa_key), а какой из них будет использован, определяет порядок в HostKeyAlgorithms клиента. При первом подключении OpenSSH показывает отпечаток SHA-256 и спрашивает, доверять ли ему; если ключ потом изменится, выводится WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! и подключение прерывается (при значении StrictHostKeyChecking по умолчанию).
Ротация ключей хоста без сбоев у клиентов: параметр UpdateHostKeys в OpenSSH (в последних версиях клиента включён по умолчанию) позволяет серверу после аутентификации сообщить все свои ключи хоста, чтобы клиенты узнали новые ключи до удаления старого. В крупных парках серверов доверия при первом подключении избегают полностью с помощью сертификатов хостов (@cert-authority в known_hosts) или записей SSHFP, подписанных DNSSEC (RFC 4255).
Если ключи хоста встроены в эталонный образ (golden image), все клонированные с него серверы подтверждают подлинность одним и тем же ключом; генерируйте ключи заново при первой загрузке. HashKnownHosts сохраняет имена хостов в хешированном виде, чтобы украденный файл known_hosts не раскрывал список ваших серверов.