SSH to Instance Failed at "Permission denied (publickey,gssapi-keyex,gssapi-with-mic)" in OCI

Applies To:

Oracle Cloud Infrastructure - Version N/A and later

Information in this document applies to any platform.

Symptoms:

When SSH'ing to an instance, this "Permission denied (publickey,gssapi-keyex,gssapi-with-mic)" error can appear:

$ ssh -i ssh_key user@<IP_ADDRESS>
FIPS integrity verification test failed.
Permission denied (publickey,gssapi-keyex,gssapi-with-mic).

Here are more logs:

$ ssh -v -i ssh_key user@<IP_ADDRESS>
FIPS integrity verification test failed.
OpenSSH_5.3p1, OpenSSL 1.0.1e-fips 11 Feb 2013
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: Applying options for *
debug1: Connecting to <IP_ADDRESS> [<IP_ADDRESS>] port 22.
debug1: Connection established.
debug1: permanently_set_uid: 0/0
debug1: identity file ssh_key type 1
debug1: identity file ssh_key-cert type -1
debug1: Remote protocol version 2.0, remote software version OpenSSH_7.4
debug1: match: OpenSSH_7.4 pat OpenSSH*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_5.3
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-ctr hmac-sha1 none
debug1: kex: client->server aes128-ctr hmac-sha1 none
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<2048<8192) sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP
debug1: SSH2_MSG_KEX_DH_GEX_INIT sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_REPLY
debug1: Host '<IP_ADDRESS>' is known and matches the RSA host key.
debug1: Found key in