Solution |
On FortiGate running firmware v7.0.12 or firmware v7.2.5, when attempting to perform SSH from an SSH tool to FortiGate firmware v7.0.12 or v7.2.5, FortiGate offers keys ssh-rsa and ssh-ed25519 as the server host keys algorithms.

ssh-rsa will no longer be offered as the server key host algorithm after upgrading to FortiOS v7.0.13 or FortiOS 7.2.6 and only offer the ssh-ed25519 algorithm.
The same key host algorithm offering can be verified in the SSH debugs:
diagnose debug console timestamp enable diagnose debug application sshd -1 diagnose debug enable
2023-10-18 10:52:20 SSH: Proposal: 0, Ciphers: 'diffie-hellman-group-exchange-sha256,curve25519-sha256@libssh.org,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521' 2023-10-18 10:52:20 SSH: Proposal: 2, Ciphers: 'chacha20-poly1305@openssh.com,aes256-ctr,aes256-gcm@openssh.com' 2023-10-18 10:52:20 SSH: Proposal: 3, Ciphers: 'chacha20-poly1305@openssh.com,aes256-ctr,aes256-gcm@openssh.com' 2023-10-18 10:52:20 SSH: Proposal: 4, Ciphers: 'hmac-sha2-256,hmac-sha2-256-etm@openssh.com,hmac-sha2-512,hmac-sha2-512-etm@openssh.com' 2023-10-18 10:52:20 SSH: Proposal: 5, Ciphers: 'hmac-sha2-256,hmac-sha2-256-etm@openssh.com,hmac-sha2-512,hmac-sha2-512-etm@openssh.com' 2023-10-18 10:52:20 SSH: list_hostkey_types: ssh-rsa,ssh-ed25519 2023-10-18 10:52:20 SSH: SSH2_MSG_KEXINIT sent 2023-10-18 10:52:20 SSH: SSH2_MSG_KEXINIT received 2023-10-18 10:52:20 SSH: kex_parse_kexinit: diffie-hellman-group-exchange-sha256,curve25519-sha256@libssh.org,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521 2023-10-18 10:52:20 SSH: kex_parse_kexinit: ssh-rsa,ssh-ed25519 2023-10-18 10:52:20 SSH: kex_parse_kexinit: chacha20-poly1305@openssh.com,aes256-ctr,aes256-gcm@openssh.com 2023-10-18 10:52:20 SSH: kex_parse_kexinit: chacha20-poly1305@openssh.com,aes256-ctr,aes256-gcm@openssh.com 2023-10-18 10:52:20 SSH: kex_parse_kexinit: hmac-sha2-256,hmac-sha2-256-etm@openssh.com,hmac-sha2-512,hmac-sha2-512-etm@openssh.com 2023-10-18 10:52:20 SSH: kex_parse_kexinit: hmac-sha2-256,hmac-sha2-256-etm@openssh.com,hmac-sha2-512,hmac-sha2-512-etm@openssh.com
FortiGate v7.0.13 and v7.2.6 offer only the ssh-ed25519 host key algorithm.

In the SSH debugs, the key host algorithm offering can be checked:
2023-10-18 10:07:52 SSH: Proposal: 0, Ciphers: 'diffie-hellman-group-exchange-sha256,curve25519-sha256@libssh.org,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp 521' 2023-10-18 10:07:52 SSH: Proposal: 2, Ciphers: 'chacha20-poly1305@openssh.com,aes256-ctr,aes256-gcm@openssh.com' 2023-10-18 10:07:52 SSH: Proposal: 3, Ciphers: 'chacha20-poly1305@openssh.com,aes256-ctr,aes256-gcm@openssh.com' 2023-10-18 10:07:52 SSH: Proposal: 4, Ciphers: 'hmac-sha2-256,hmac-sha2-256-etm@openssh.com,hmac-sha2-512,hmac-sha2-512-etm@openssh.com' 2023-10-18 10:07:52 SSH: Proposal: 5, Ciphers: 'hmac-sha2-256,hmac-sha2-256-etm@openssh.com,hmac-sha2-512,hmac-sha2-512-etm@openssh.com' 2023-10-18 10:07:52 SSH: list_hostkey_types: ssh-ed25519 2023-10-18 10:07:52 SSH: SSH2_MSG_KEXINIT sent 2023-10-18 10:07:52 SSH: SSH2_MSG_KEXINIT received 2023-10-18 10:07:52 SSH: kex_parse_kexinit: diffie-hellman-group-exchange-sha256,curve25519-sha256@libssh.org,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521 2023-10-18 10:07:52 SSH: kex_parse_kexinit: ssh-ed25519 2023-10-18 10:07:52 SSH: kex_parse_kexinit: chacha20-poly1305@openssh.com,aes256-ctr,aes256-gcm@openssh.com 2023-10-18 10:07:52 SSH: kex_parse_kexinit: chacha20-poly1305@openssh.com,aes256-ctr,aes256-gcm@openssh.com 2023-10-18 10:07:52 SSH: kex_parse_kexinit: hmac-sha2-256,hmac-sha2-256-etm@openssh.com,hmac-sha2-512,hmac-sha2-512-etm@openssh.com 2023-10-18 10:07:52 SSH: kex_parse_kexinit: hmac-sha2-256,hmac-sha2-256-etm@openssh.com,hmac-sha2-512,hmac-sha2-512-etm@openssh.com
Note:
rsa-sha2-256 and rsa-sha2-512 were added to v7.0.14.
- The host key types available in version 7.2.8 are rsa-sha2-512 and ssh-ed25519.

- The host key type rsa-sha2-256 was added in v7.2.9 and subsequent versions.

Related article:
How SSH Server host key algorithms can be changed
|