The Error:

no matching host key type found. Their offer: ssh-rsa

The reason: in the OpenSSH 8.2 release notes there is a statement:

we will be disabling the “ssh-rsa” public key signature algorithm that depends on SHA-1 by default in a near-future release.

This change is now appearing as updates deploy, I noticed it with the MacOS Ventura 13.0.1 which if you run the command (capital V for Version):

ssh -V

now returns 9.0p1. Monteray 12.6.2 by contrast returns 8.6p1.

While the best path is to update the endpoint/server/device that you are connecting to, if you cannot do that then you can workaround it by using the SSH config file.

create or edit the file using nano or your preferred editor:

nano ~/.ssh/config

Add in the following text"

Host [hostname or IP Address]
  HostkeyAlgorithms +ssh-rsa
  PubkeyAcceptedAlgorithms +ssh-rsa

You can now connect to that host again.

This is a Good Security update, but it will trip things up for a little while until patches are available and updated across a very wide range of devices and endpoints.

Addendum:

If you want to simplify your SSH command, do this in the .ssh/config file:

Host [easy to remember name]
  Hostname [hostname or IP address]
  User [username]
  HostkeyAlgorithms +ssh-rsa
  PubkeyAcceptedAlgorithms +ssh-rsa

Now instead of

ssh user@host

you can just

ssh [easy to remember name]

I learned something today!