Ssh – AWS Host Key Verification Failed

I have had some trouble sshing into any AWS EC2 instance the past few days. Last Wednesday (four days ago) I was able to log into an EC2 just fine and install Jenkins using Docker. Thursday morning I tried to log into the same EC2 and received "Host key verification failed." Since then I have tried the following:

• Double-checked my inbound rules on the EC2 to validate access is allowed on port 22
• Double-checked the Network ACL on the subnet to validate access is allowed on port 22
• Removed my ~/.ssh/known_hosts file on my Mac thinking it could have been an RSA key issue like the one described here. To my understanding the known_hosts file would be recreated on a successful connection.
• Started a second EC2 that was a clone of the first (CentOS 7 Community AMI, ami-b81dbfc5) and attempted to SSH in that EC2 (fail)
• Started a third EC2 that was a clone of the first but uses a new pem file (fail)
• Switched laptops to my Ubuntu 16.04 and used the second pem file to attempt to connect to the third EC2 (fail)
• Launched Amazon's standard AMI (ami-467ca739) with the default configurations and attempted to connect to that EC2 using the second pem file from the Ubuntu machine (fail)

Note that the first two EC2 attempts had an Elastic IP associated with those VMs. The last two EC2s did not have an Elastic IP associated with them in case that was the source of the issue. All EC2s are deployed in the Northern Virginia region and were deployed within the same VPC.

For what it's worth, I was hoping to log into the EC2 in order to add the Jenkins user to the Docker user group. I am trying my hand at setting up a devops pipeline. However not being able to log into, apparently, any EC2 is the fundamental issue and the core blocker.

Below is some verbose output in the ssh attempt. I am having trouble thinking through what else I can try, but typically when that happens it means I've overlooked something 🙂 . Any ideas what would prevent multiple clients from being able to log into any EC2 in a region? Network ACL on the subnet and inbound rules on the EC2 are all I can think of, but those are open, as mentioned previously. It's probably more likely I'm not understanding the verbose output to know the next action to try. Thanks in advance!

public:pem-files$ ssh -i fresh-ec2-test-180513.pem ec2-user@ec2-18-205-21-67.compute-1.amazonaws.com -v
OpenSSH_7.2p2 Ubuntu-4ubuntu2.4, OpenSSL 1.0.2g  1 Mar 2016
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: Applying options for *
debug1: Connecting to ec2-18-205-21-67.compute-1.amazonaws.com [18.205.21.67] port 22.
debug1: Connection established.
debug1: key_load_public: No such file or directory
debug1: identity file fresh-ec2-test-180513.pem type -1
debug1: key_load_public: No such file or directory
debug1: identity file fresh-ec2-test-180513.pem-cert type -1
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_7.2p2 Ubuntu-4ubuntu2.4
debug1: Remote protocol version 2.0, remote software version OpenSSH_7.4
debug1: match: OpenSSH_7.4 pat OpenSSH* compat 0x04000000
debug1: Authenticating to ec2-18-205-21-67.compute-1.amazonaws.com:22 as 'ec2-user'
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: algorithm: curve25519-sha256@libssh.org
debug1: kex: host key algorithm: ecdsa-sha2-nistp256
debug1: kex: server->client cipher: chacha20-poly1305@openssh.com MAC: <implicit> compression: none
debug1: kex: client->server cipher: chacha20-poly1305@openssh.com MAC: <implicit> compression: none
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
debug1: Server host key: ecdsa-sha2-nistp256 SHA256:oeuVV0FGR89PJZvDi+oFvE+ltn5hN8T1Gtf6EjhUC9w
The authenticity of host 'ec2-18-205-21-67.compute-1.amazonaws.com (18.205.21.67)' can't be established.
ECDSA key fingerprint is SHA256:oeuVV0FGR89PJZvDi+oFvE+ltn5hN8T1Gtf6EjhUC9w.
Are you sure you want to continue connecting (yes/no)? 
Host key verification failed.