SSH server gives "userauth_pubkey: key type ssh-rsa not in PubkeyAcceptedAlgorithms [preauth]" when connecting with PuTTY

I have built a new Ubuntu server in AWS. Now for some reason my private key that works on other Ubuntu servers is not working here. The error in auth.log is:

userauth_pubkey: key type ssh-rsa not in PubkeyAcceptedAlgorithms [preauth]

This is an issue only with PuTTY; if I try logging in via a Linux workstation, there are no issues at all with any machine. The difference I see is the new server is Ubuntu 22.04.1 LTS running “OpenSSH_8.9p1 Ubuntu-3, OpenSSL 3.0.2 15 Mar 2022”. The working (old) server is Ubuntu 20.04.4 LTS (Focal Fossa) running “OpenSSH_8.2p1 Ubuntu-4ubuntu0.4, OpenSSL 1.1.1f 31 Mar 2020”. Has something changed in this version of OpenSSH?  How do I get PuTTY working again?