Versions of NoMachine software prior to 5.1.22 were using a DSA private key to authenticate on the remote host in some specific cases:

i) Connections by SSH protocol + NoMachine login

ii) Adding a remote node to the main server ('nxserver --nodeadd' command)

iii) Connections by NX Client 3.5.0

When the remote system has OpenSSH v. 7.0 or later installed, the SSH server is configured by default to refuse DSA keys: NoMachine connections therefore hang or get a timeout. 

OpenSSH v. 7.0 has disabled by default the ssh-dss (DSA) public key algorithm:  

" Support for ssh-dss, ssh-dss-cert-* host and user keys is disabled by default at run-time. These may be re-enabled using the instructions at http://www.openssh.com/legacy.html"

(http://www.openssh.com/txt/release-7.0)

Possible solutions are:

1) Upgrade NoMachine client and NoMachine server side installations to the last version. 

NoMachine uses a RSA key:  https://www.nomachine.com/FR04N03093 since v. 5.1.22.

or

2)  Re-enable support for DSA keys in the SSHD configuration.

This is possible with OpenSSH v. 7.0 and v. 7.1 and until OpenSSH maintains compatibility with old DSA keys.

To re-enable support for DSA keys, add this line at the end of the SSHD configuration file, namely /etc/ssh/sshd_config: