OK, the problem isn't with the key, it is with Putty.
I use both Windows and Linux to connect to instances. It is just the way I've evolved
to work over many years.
When I connect to the instance using a modern Linux (CentOS 7) using my existing key, the
connection works (sshd logs on the f33 instance:)
Nov 10 04:15:15 ip-x-x-x-x sshd[7204]: Accepted publickey for fedora from x-x-x-x port
43114 ssh2: RSA SHA256:xxxxxx
When I take the same key, import it into Putty's puttygen, save it in Putty's
format, and use it to log into the same server, I get "too many auth failures",
and the log file shows this:
Nov 10 04:34:10 ip-x-x-x-x sshd[7402]: userauth_pubkey: key type ssh-rsa not in
PubkeyAcceptedKeyTypes [preauth]
I had this problem locally too, when I upgraded an f32 box to f33, but I "fixed"
it by moving to an ed25519 key. I assumed that the key type was the fix. I was wrong:
the hash algorithm is the issue.
I'm not sure what Putty is doing wrong: I don't know if it "imports" the
hash from the key. I did this on my actual key (on Centos):
ssh-keygen -l -f id_rsa_jeffs_aws_2018-07-10
2048 SHA256:xxx no comment (RSA)
and the hash provided there matches the hash showed in the successful login log line
(obviously). So Putty is somehow taking that key and presenting it "wrong".
Regardless: this isn't a Fedora Cloud problem. It isn't a Fedora problem at all,
but a Putty problem.
I'm sorry for the noise. Hopefully this chain will help someone else if they have the
same issues that I have had and come to the same wrong conclusion.
Kevin