I created an AWS EC2 instance (ubuntu 20.04), and associated it with my key pair (that is already on AWS). Thus I could connect with SSH for several days. However, when I went to connect today, I get the message:

ubuntu@x.x.x.x: Permission denied (publickey,gssapi-keyex,gssapi-with-mic).

I have checked everything, and the error persists. And this is not the first time this has happened. Ever since I started seriously using EC2 two months ago, this exact problem has happened several times. Usually the only solution is to save the instance as a template and re-create it again.

This seems very strange. Is this an AWS bug or what?