When you ssh to a new EC2 instance, you are presented with the challenge:
The authenticity of host 'XXX' can't be established. RSA key fingerprint is YYY. Are you sure you want to continue connecting (yes/no)?
For optimal security, you are supposed to request the instance console output and find the ssh host key fingerprint in the log to verify that it is the same as the fingerprint presented to you by the ssh command.