No Matching Host Key Type Found After Upgrading to OpenSSH 8.8

I updated openssh with Homebrew on my Mac, and after the version went up I could no longer connect, with the error below.

ERROR: Unable to negotiate with 192.168.1.10 port 22: no matching host key type found. Their offer: ssh-rsa,ssh-dss

The error did not appear for every destination; the ones I could no longer reach were those running relatively old operating systems.

• SSH that can connect

$ ssh -V
OpenSSH_8.4p1 Debian-5, OpenSSL 1.1.1k  25 Mar 2021

• SSH that cannot connect

$ ssh -V
OpenSSH_8.9p1, OpenSSL 1.1.1n  15 Mar 2022

Looking into it, the cause is that RSA keys with SHA-1 have been disabled since OpenSSH8.8

The solution

Create .ssh/config with the content below, or add HostKeyAlgorithms and PubkeyAcceptedAlgorithms to it

Host HOST-NAME(any name you like)
Hostname FQDN or IP
IdentityFile ~/.ssh/id_rsa
IdentitiesOnly yes
HostKeyAlgorithms=+ssh-rsa
PubkeyAcceptedAlgorithms=+ssh-rsa

Incidentally, on an old SunOS I also had to add the following lines.

KexAlgorithms +diffie-hellman-group1-sha1
Ciphers aes128-cbc

A caveat

In my environment I have a lot of machines running Mac and Linux, so I manage my SSH keys with Git.
When they are managed with Git, if the SSH on the PC you are using is older than 8.8, applying the solution above will instead make it impossible to connect.

/home/user/.ssh/config: line 13: Bad configuration option: pubkeyacceptedalgorithms

It would be fine if it ignored the invalid option and still connected, but not being able to connect at all is a real nuisance.

For the time being, I decided to create a branch in Git so that it can be used both with OpenSSH8.8 and later and with older versions.
Once Linux ships OpenSSH 8.8 or later by default, I can just merge them.