SSH fails from host to host on same tenant

Issue

• SSH from vm to vm on the same compute host is working as expected

• SSH from vm to vm on different compute host is not working and fails initiating a SSH session with the following output:

debug3: order_hostkeyalgs: prefer hostkeyalgs: ecdsa-sha2-nistp256-cert-v01@openssh.com,ecdsa-sha2-nistp384-cert-v01@openssh.com,ecdsa-sha2-nistp521-cert-v01@openssh.com,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521
debug1: SSH2_MSG_KEXINIT 

• Adding new vms on different host on the same and different network within a tenant fails with similar message.

• SSH via external floating IP is fully functionnal

• SSHing to previously existing VMs is randomly functionnal

• SSHing to new VMs is not functionnal