How to investigate causes for a very slow telnet?
This indicates an issue with the IPv6 address configuration.
Normally, if IPv6 is not configured at all, then IPv6 addresses aren't tried when you're trying to connect to any other host.
However, if IPv6 is, in fact, configured, but is configured incorrectly, then the problems as you describe will appear.
Solution:
You either have to disable IPv6 at all (make sure it is not configured at all), or make sure that if it is configured, then the configuration is applied correctly.