We have upgraded our internal tmate server to
tmate-ssh-server-2.3.0~git44.e1a5e084-7.1.x86_64 and now no new client running
Leap 15.1 can connect to it (clients that where already "known" by the server
are ok).

The error only happens on Leap which have tmate-2.2.1-lp151.2.4.x86_64
On Tumbleweed it's working because it has a newer tmate version:
tmate-2.4.0-1.1.x86_64
(I used new clean and up to date virtual machines for Leap and Tumbleweed to
test it)

The error is: [tmate] Reconnecting... (Cannot authenticate server)

And there is a bug on upstream about that:
https://github.com/tmate-io/tmate/issues/164