I'm seeing this same issue with some instances. The instance typically works fine for a while and oftentimes never has the issue, but then I get this error. I'm not sure what is happening to my instances - it seems like a bug. A couple weeks ago it seemed like most of my instances had this issue after a couple days of ssh ing into them without problems.

I am trying to connect to a CentOS EC2 instance from my WIN 11 machine and am facing the same issue you have reported. Have been trying for the last 2 days but no luck. kindly share your inputs if you were able to resolve it.

$ ssh -i "CentOSStream9.pem" centos@ec2-xx-xx-xx-xxx.us-east-2.compute.amazonaws.com centos@ec2-xx-xx-xx-xxx.us-east-2.compute.amazonaws.com: Permission denied (publickey,gssapi-keyex,gssapi-with-mic).