SSH - Permission denied (publickey)

Solution 1:

Recent releases from RedHat governed distributions disable some of the cryptographic algorithms considered obsolete or insecure.

Judging from the line:

debug1: send_pubkey_test: no mutual signature algorithm

your server is probably using one of these disabled algorithms and doesn't allow something your client considers secure.

The systemwide crypto consiguration is setup by update-crypto-policies command and the default is DEFAULT.

You can enable most (if not all) of obsolete/insecure algorithms by downgrading to LEGACY crypto policy:

update-crypto-policies --set LEGACY

Saying the above, please consider upgrading your old server to something more modern.