サーバーは通常、アルゴリズムごとに 1 つのホスト鍵を持ち（/etc/ssh/ssh_host_ed25519_key、…_ecdsa_key、…_rsa_key）、どれが使われるかはクライアントの HostKeyAlgorithms の順序で決まります。初回接続時、OpenSSH は SHA-256 フィンガープリントを表示して信頼するかどうかを尋ねます。それ以降にホスト鍵が変わると WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! が表示され、接続は中止されます（StrictHostKeyChecking がデフォルトのままの場合）。
クライアントに影響を与えずにホスト鍵をローテーションする方法として、OpenSSH の UpdateHostKeys（最近のクライアントではデフォルトで有効）があります。これにより、サーバーは認証後に自身のすべてのホスト鍵を通知でき、クライアントは古い鍵が削除される前に新しい鍵を把握できます。多数のサーバーを運用する環境では、ホスト証明書（known_hosts の @cert-authority）や、DNSSEC で署名された SSHFP レコード（RFC 4255）を使うことで、初回接続時に信頼する方式を完全に回避できます。
ホスト鍵を組み込んだゴールデンイメージを使うと、複製したすべてのサーバーが同じ身元を持つことになります。鍵は初回起動時に再生成してください。HashKnownHosts はホスト名をハッシュ化して保存するため、known_hosts ファイルが盗まれても、サーバーの一覧が漏れることはありません。