Compute Engineのインスタンスに自端末のSSHクライアントから接続する際は
メタデータのSSH認証鍵を登録してあげる必要があります。

[Compute Engine]-[メタデータ]-[SSH 認証鍵]にて鍵を登録します。

この時登録する鍵の情報は以下のフォーマットに合わせる必要があります。

ssh-rsa [KEY_VALUE] [USERNAME]

私は最初マニュアルをしっかり読まなかったためフォーマットの存在を知らずハマりました・・・・

参考

その他

メタデータからの鍵登録ではなく直接インスタンスの authorized_keys に鍵を登録してもSSH接続はできましたが、インスタンス再起動の度に上書きされるようでした。