Problem connecting from a Debian 11 Bullseye to an old OpenWRT Chaos Calmer:

ssh root@192.168.31.45
Unable to negotiate with 192.168.31.45 port 22:
    no matching key exchange method found.
    Their offer: diffie-hellman-group14-sha1,diffie-hellman-group1-sha1,kexguess2@matt.ucc.asn.au

You can edit your $HOME/.ssh/config file and put ah Host stanza like this:

Host hostname hostname.domain.tld 192.168.31.45
    KexAlgorithms +diffie-hellman-group1-sha1

This will force the use of diffie-hellman-group1-sha1 key exchange method, which is considered less secure nowday.

Problem connecting from an Android environment with Termux version 0.118.0 (February 2022) to an old Debian 6 Squeeze:

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

So the first option to add is HostKeyAlgorithms, but there is another and more subtle problem, because no error message is printer unless you add the -v option (for verbose),

debug1: send_pubkey_test: no mutual signature algorithm
debug1: No more authentication methods to try.
root@192.168.0.250: Permission denied (publickey).

So also the PubkeyAcceptedKeyTypes is required:

ssh -o HostKeyAlgorithms=+ssh-rsa -o PubkeyAcceptedKeyTypes=+ssh-rsa root@192.168.0.250