【結論】
・古いホストキーアルゴリズムが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をサポートさせる手順も記載しておりますが、セキュリティレベルが低下する為、本記事では扱いません。