Host key validation is taking somewhere between 8-10 minutes for me. I think this is because the EC2 console output is not updated regularly, in my tests using the AWS CLI has taken around 8 minutes for the console output to be updated after starting an instance. Using the --latest CLI option reduces the time taken to get the host key through the AWS CLI substantially.