ssh: impossible to access from outside (RHEL 7)...:(

Dear all,

good morning.
I have installed RHEL 7 on my Dell workstation.
I have allowed the ssh service through the firewall, but it is impossible to access to the workstation.
In particular, the behavior of ssh is different according to the other machine which tries to connect from inside the same network:

Machine "1":
the first time it connected via ssh;
shutting down the connection and re-connecting back from Machine "1", it says "Connection timed out" and never connects any more from Machine "1";

Machine "2":
the first time connected via ssh;
shutting down the connection and (immediately) re-connecting back from Machine "2", the following message appears:
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that a host key has just been changed.
The fingerprint for the RSA key sent by the remote host is
6e:45:f9:a8:af:38:3d:a1:a5:c7:76:1d:02:f8:77:00.
Please contact your system administrator.

and never connects more from Machine "2"....

Please, what can I do?
It is mandatory for me to make these machine dialogue with each other...
Is there something I have to do with iptables, even though I have put as "secure" the ssh service in the firewall?

Thanks in advance and my best regards

Giacomo