ansible tower - command works BUT playbook fails to connect to the host via ssh

In my ansible tower I can execute a command successfully on a remote server, however when I try to run a playbook I get:

{
"msg": "Failed to connect to the host via ssh: Warning: Permanently added 'hostname,10.1.4.66' (ECDSA) to the list
of known hosts.\r\nPermission denied (publickey,gssapi-keyex,gssapi-with-mic,keyboard-interactive).",
"unreachable": true,
"changed": false
}

Seems to be a weird issue, did someone saw and solved this before?

This group is dedicated to Ansible itself, not Tower or AWX.

Please contact RedHat support.

Regards
        Racke

Try to run with sudo?