OpenSSH 8.8, released in September 2021, turned off the ssh-rsa public key signature algorithm by default because it depends on SHA-1. The symptom is an abrupt 'Permission denied (publickey)' against a server that worked yesterday, sometimes preceded by 'no mutual signature algorithm' with LogLevel DEBUG1.
The key type is not the problem. An RSA key is still fine as long as both ends can negotiate rsa-sha2-256 or rsa-sha2-512, which servers running OpenSSH 7.2 and later support. Only genuinely old servers, and some appliances and Git hosting on legacy firmware, are affected.
Diagnose with 'ssh -v host' and look at the offered signature algorithms. The correct fix is to upgrade the server. The stopgap is a targeted client config block: 'PubkeyAcceptedAlgorithms +ssh-rsa' and, if the host key itself is RSA with SHA-1, 'HostkeyAlgorithms +ssh-rsa'. Use the leading plus so you append to the default list rather than replacing it, and scope the block to that one host, never to 'Host *'.