再インストールしたLinuxサーバに対して、Linuxクライアントから公開鍵認証でSSH接続を行ったところ以下のメッセージが出ました。

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that a host key has just been changed.
The fingerprint for the ED25519 key sent by the remote host is
SHA256:********************************
Please contact your system administrator.
Add correct host key in /home/hoge/.ssh/known_hosts to get rid of this message.
Offending ECDSA key in /home/hoge/.ssh/known_hosts:2
Host key for hoge.example.com has changed and you have requested strict checking.
Host key verification failed.

それに備えて秘密鍵を新しいものに差し替えていましたが、サーバが再インストール前の公開鍵情報を覚えていたという形です。

「SSHホスト鍵が変わってるよ！」と怒られたときの対処

上記そのものズバリの解決策がありましたので、これに沿って対応していきます。

エラーが起きたLinuxクライアントで

ssh-keygen -R hoge.example.com

を実行するだけ。(ホスト名は自分の環境に合わせます）

# Host hoge.example.com found: line 1
# Host hoge.example.com found: line 2
/home/hoge/.ssh/known_hosts updated.
Original contents retained as /home/hoge/.ssh/known_hosts.old

のメッセージが出てきたら対処完了です。

改めて、新たな秘密鍵を用いて

ssh -i /path/to/private/key/hoge.exammple.com.key hoge@hoge.example.com

等としてssh接続を行い、

This key is not known by any other names.
Are you sure you want to continue connecting (yes/no/[fingerprint])? yes

と、無事に接続ができました。