次の３パターンが考えられる
1. 間違った鍵で接続しようとしている。キーペアは正しいか確認する
2. 間違ったユーザー名で接続しようとしている。正しいユーザー名かどうか確認する
3. インスタンス内のSSH設定が正しいかどうか確認する。

インスタンス内のSSH設定を確認

/etc/ssh/sshd_config

PermitRootLogin no
PubkeyAuthentication yes
PasswordAuthentication yes
PermitEmptyPasswords yes

設定を変えたら再起動

$ sudo service sshd restart

PermitRootLogin

rootユーザーでのログインを許可する設定。確認後はnoにすべき。
アプリケーションの都合でどうしてもrootユーザーでのログインが必要な場合はMatchを使ってクライアントを絞る。

PermitRootLogin no
Match Address 10.0.0.1
PermitRootLogin yes
PubkeyAuthentication

公開鍵認証を許可する設定。RSA鍵で認証するならyes。
noになってるとたぶんPermission denied(publickey)にはならずにパスワードを聞かれる。

PasswordAuthentication

パスワード認証を許可する設定。yesだとブルートフォース攻撃の的に。

PermitEmptyPasswords

パスワード認証の場合に空パスワードを許可するかどうか。
鍵のパスフレーズとは無関係。