SSH authentication fails to work after having worked previously

Since you are getting Permission denied, you know your security groups are configured to allow the traffic. It would be helpful if you pasted the exact error you receive.

Make sure you are using the right default user name for your AMI https://docs.aws.amazon.com/AWSEC2/latest/UserGuide/connection-prereqs.html

In the EC2 console, you can look at the details of the instance and make sure you are using the correct Key pair name.

The error message you mention indicates that the (public) encryption key stored on the instance for the user that you're trying to log into the instance with doesn't match the (private) encryption key that you have on your laptop or local host.

I would suggest doing some forensics on the root volume of an instance which has stopped working: Take the volume and mount it on another instance which is working, then look at the private key to see if it is the right key; look at the time/date stamp; look at logs to see if there was some process or user that changed it.

Does anyone else have access to your private/public keypair? If so, generate a new keypair and delete the old one.