RHEL 9 no longer lets you ssh to RHEL ≤ 6 hosts out of the box. You can weaken security of the whole system but there’s no easy way to set security policy per remote host. Here’s how to set up ssh so it works for a RHEL 5 or RHEL 6 host:
First edit your .ssh/config file, adding an entry for the host:
Host rhel5or6-host
KexAlgorithms +diffie-hellman-group14-sha1
MACs +hmac-sha1
HostKeyAlgorithms +ssh-rsa
PubkeyAcceptedKeyTypes +ssh-rsa
PubkeyAcceptedAlgorithms +ssh-rsa
(The lines except the first “Host” line should be indented. WordPress screws up the formatting …)
That’s not enough on its own, because RHEL 9 also maims the openssl library by disabling SHA1 support by default. To fix that, create /var/tmp/openssl.cnf with:
.include /etc/ssl/openssl.cnf
[openssl_init]
alg_section = evp_properties
[evp_properties]
rh-allow-sha1-signatures = yes
Now you can ssh to RHEL 5 or RHEL 6 hosts like this:
OPENSSL_CONF=/var/tmp/openssl.cnf ssh rhel5or6-host
Thanks Laszlo Ersek for working out most of this. Related bugs:
2064740 – RFE: Make it easier to configure LEGACY policy per service or per host
Richard WM Jones 
Hi,
Thank you for this – it worked perfectly for connecting Oracle Linux 9 boxes to old centOS 6.x machines.
Hi,
A brief note on this approach, since it’s linked from an answer on ServerFault (/a/1149768). It works – thank you very much for that – but can be simplified.
Please note: My case is connecting from an OL/RHEL 9.1 client (OpenSSH 8.7p1) to a RHEL 6 server (OpenSSH 5.3p1). I have not tested this against a RHEL 5 or older server.
As you mention, on RHEL 9 the openssl.cnf addition/alternative is required. However, I found that this also removed the need for the KexAlgorithms and MACs changes in the client config. I also didn’t need to change HostKeyAlgorithms (the docs mention that this is limited to the set allowed by PubkeyAcceptedAlgorithms, so adding it there suffices), and PubkeyAcceptedKeyTypes is an older synonym for PubkeyAcceptedAlgorithms so you only need one of those two.
tl;dr: with the openssl.cnf changes in place, the only SSH config entry you need is “PubkeyAcceptedAlgorithms +ssh-rsa”.