Failed connection with SSH servers and clients that do not support the 'server-sig-algs' extension

Issue

• Red Hat Enterprise Linux 9 clients can’t connect to SSH servers that don’t support the server-sig-algs extension nor ECDSA hostkeys. (a, b)
• Legacy SSH clients not supporting server-sig-algs extension can not connect to Red Hat Enterprise Linux 9 servers using RSA authentication keys (c, d)

a) The Red Hat Enterprise Linux 9 client connecting to Legacy server supporting only ssh-rsa signature algorithm with SHA1 and providing only RSA hostkey:

$ ssh user@example.com
The authenticity of host 'example.com (1.2.3.4)' can't be established.
RSA key fingerprint is SHA256:ycznxddL1KwSN1Wbih1 UDfPntj5pM1a/kpPKLGgPzEI.
This key is not known by any other names
Are you sure you want to continue connecting (yes/no/[fingerprint])? yes
Warning: Permanently added 'example.com' (RSA) to the list of known hosts.
ssh_dispatch_run_fatal: Connection to 5.6.7.8 port 22: error in libcrypto

b) The Red Hat Enterprise Linux 9 client connects to a Legacy server supporting only the ssh-rsa signature algorithm, but provides different hostkeys. The client tries to authenticate with RSA key:

$ ssh -vvv user@example.com
[...]
debug1: Next authentication method: publickey
debug1: Offering public key: /root/.ssh/id_rsa RSA SHA256:+z5NN8Z6RfNykL5l6Ht2Cbjj16xGp76TjILrQ4Cftqk
debug1: send_pubkey_test: no mutual signature algorithm
[...]
debug1: No more authentication methods to try.
user@example.com: Permission denied (publickey).

c) The Red Hat Enterprise Linux 9 server can not provide SHA1 signature for the connecting legacy clients (example RHEL6) that negotiate RSA hostkey verification:

$ ssh -vvv example.com
[...]
debug2: kex_parse_kexinit: ssh-rsa-cert-v01@openssh.com,ssh-dss-cert-v01@openssh.com,ssh-rsa-cert-v00@openssh.com,ssh-dss-cert-v00@openssh.com,ssh-rsa,ssh-dss
[...]
debug2: kex_parse_kexinit: rsa-sha2-512,rsa-sha2-256,ecdsa-sha2-nistp256,ssh-ed25519
[...]
debug1: kex: server->client aes128-ctr hmac-sha1 none
debug2: mac_setup: found hmac-sha1
debug1: kex: client->server aes128-ctr hmac-sha1 none
no hostkey alg

d) The legacy client authenticates to Red Hat Enterprise Linux 9 using RSA authentication key.

$ ssh -vvv example.com
[...]
debug2: kex_parse_kexinit: hmac-sha1,umac-64@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-ripemd160,hmac-ripemd160@openssh.com,hmac-sha1-96
[...]
debug2: kex_parse_kexinit: hmac-sha2-256-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-sha2-256,hmac-sha1,umac-128@openssh.com,hmac-sha2-512
[...]
debug2: mac_setup: found hmac-sha1
debug1: kex: server->client aes128-ctr hmac-sha1 none
debug2: mac_setup: found hmac-sha1
debug1: kex: client->server aes128-ctr hmac-sha1 none
no hostkey alg