RHEL9: Cannot connect to legacy systems, getting error message "no matching host key type found. Their offer: ssh-rsa"

Solution Verified - Updated 2025-04-10T08:48:14+00:00 -

Issue

Trying to connect from a RHEL9 system in FIPS mode or even with DEFAULT crypto policy to a legacy system (RHEL6, HP iLO, etc.), the following error message is displayed
```
(RHEL9) $ ssh <legacy-system>
Unable to negotiate with IPAddr port 22: no matching host key type found. Their offer: ssh-rsa
```
Trying to connect from a RHEL8 system works fine

A Red Hat subscription provides unlimited access to our knowledgebase, tools, and much more.