Crappy SSH implementations (like Mikrotik) support only old and broken ciphers that are now blocked by default in openssh client. This has been fixed in recent versions of Mikrotik firmware.
Add this to your .ssh/config.
Host foo.bar.sk PubkeyAcceptedKeyTypes ssh-rsa,ssh-dss* KexAlgorithms +diffie-hellman-group1-sha1 HostKeyAlgorithms=+ssh-dss
Edit DH_GRP_MIN in dh.h. I have not found any runtime config option for this.