Servers typically hold one host key per algorithm (/etc/ssh/ssh_host_ed25519_key, …_ecdsa_key, …_rsa_key), and the client's HostKeyAlgorithms order decides which one is used. On first contact OpenSSH shows the SHA-256 fingerprint and asks whether to trust it; afterwards a change produces WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! and the connection stops (with StrictHostKeyChecking at its default).
Rotating host keys without breaking clients: OpenSSH's UpdateHostKeys (on by default in recent clients) lets a server announce all its host keys after authentication so clients learn new ones before the old one is removed. Fleets avoid first-use trust entirely with host certificates (@cert-authority in known_hosts) or DNSSEC-signed SSHFP records (RFC 4255).
Golden images that bake in host keys give every cloned server the same identity; regenerate keys on first boot. HashKnownHosts stores host names hashed so a stolen known_hosts file does not list your servers.