NCM will not connect via SSH

I am able to connect via Putty/SSH from the server NCM is installed on without have do to anything special.

Trying to connect to a Palo Alto Firewall and we get this message from the SSH applet in NCM and when trying to test the credentials. (Ip Hidden)

Connecting to the host ....                                                     
Connecting to the host 10.xx.xx.xx ....                                          
Connection/authentication to 10.xx.xx.xx failed                                  
Unable to connect, check the host server and the credentials.                   
Failed to connect.