【結論】
　・古いホストキーアルゴリズムがAmazon Linux 2023では無効化されていた。
　・クライアント側（Teraterm-4.106）が新しいアルゴリズムに未対応だった。

【対処】
方法①
teraterm-5.0-beta1にアップグレードする。

以下アルゴリズムであれば接続可能。
　・rsa-sha2-256
　・rsa-sha2-512

teraterm-5.0-beta1は対応している。

Teraterm-4.106は対応していない。

方法②
キーペアのタイプを「ED25519」で作成したキーを使ってEC2を作成する。

【参考】
https://docs.aws.amazon.com/linux/al2023/ug/ssh-host-keys-disabled.html
※上記ページにssh-rsaをサポートさせる手順も記載しておりますが、セキュリティレベルが低下する為、本記事では扱いません。