Cannot log in with ec2-user

Which version of Windows and PuTTY are you running? From your screenshot the Windows version looks quite old, so it's likely your problem is caused by a cipher mis-match.

RHEL9 has deprecated some old & insecure encryption algorithms, but when attempting the initial key exchange PuTTY is still likely offering up these.

You can prove the keys are good by spinning up an EC2 running RHEL6 or 7 and confirm that you can login with the key on these older versions of Linux.

Then you could use this new RHEL7 host as a sort of bastion to get yourself access to the RHEL9 host (though that costs money, so consider using Amazon Linux 2 which is cheaper), assuming you can't upgrade Windows/PuTTY to something that can get you connected directly.

You will likely find the same happens with EC2s running new versions like Amazon Linux 2023 and Fedora 37.

See https://access.redhat.com/documentation/en-us/red_hat_enterprise_linux/9/html/security_hardening/using-the-system-wide-cryptographic-policies_security-hardening for advice on downgrading the security of your RHEL9 instance.

Thank you. I was able to log in with ec2-user after upgrading my Putty on the client Windows machine.