Got this message a while back and it took a lot of looking to find the answer, so here it is! This assumes you have transferred over your existing keys and all the permissions etc are set up correctly.

mrn@ubuntu:/home/mrn# ssh mrn@example.com
Unable to negotiate with 123.123.123.123 port 22: no matching host key type found. Their offer: ssh-rsa,ssh-dss

Check where the configuration file is:

mrn@ubuntu:/home/mrn# ssh -vT mrn@example.com
OpenSSH_8.9p1 Ubuntu-3ubuntu0.6, OpenSSL 3.0.2 15 Mar 2022
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: include /etc/ssh/ssh_config.d/*.conf matched no files
debug1: /etc/ssh/ssh_config line 21: Applying options for *
debug1: Connecting to example.com [123.123.123.123] port 22.
debug1: Connection established.
debug1: identity file /home/mrn/.ssh/id_rsa type -1
debug1: identity file /home/mrn/.ssh/id_rsa-cert type -1
debug1: identity file /home/mrn/.ssh/id_ecdsa type -1
debug1: identity file /home/mrn/.ssh/id_ecdsa-cert type -1

Weird, it does not mention that it checks my local folder's .ssh folder, like my laptop does:

mrn@ubuntu:~ mrn $ ssh -vT mrn@example.com
OpenSSH_9.6p1, LibreSSL 3.3.6
debug1: Reading configuration data /home/mrn/.ssh/config  <-----
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 21: include /etc/ssh/ssh_config.d/* matched no files
debug1: /etc/ssh/ssh_config line 54: Applying options for *
debug1: Authenticator provider $SSH_SK_PROVIDER did not resolve; disabling
debug1: Connecting to example.com port 22.

I'm try it in /home/mrn/.ssh/config anyway, I'm sure it will be fine :)

Add the magic incantation:

Host example.com
    HostKeyAlgorithms +ssh-rsa
    PubkeyAcceptedKeyTypes +ssh-rsa

Confirm that it is looking at the config file and confirm that it now connects:

mrn@ubuntu:~/.ssh# ssh -vT mrn@example.com
OpenSSH_8.9p1 Ubuntu-3ubuntu0.6, OpenSSL 3.0.2 15 Mar 2022
debug1: Reading configuration data /home/mrn/.ssh/config
debug1: /home/mrn/.ssh/config line 1: Applying options for example.com
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: include /etc/ssh/ssh_config.d/*.conf matched no files
debug1: /etc/ssh/ssh_config line 21: Applying options for *
debug1: Connecting to example.com [123.123.123.123] port 22.
...
debug1: Next authentication method: publickey
debug1: Offering public key: /home/mrn/.ssh/id_rsa RSA SHA256:abcdefghijklmnopqrstuv/abcdefghijklmnopq/x0
debug1: Server accepts key: /home/mrn/.ssh/id_rsa RSA SHA256: abcdefghijklmnopqrstuv/abcdefghijklmnopq/x0
Authenticated to example.com ([123.123.123.123]:22) using "publickey".