I thought the replacement of Telnet with OpenSSH was fairly fast? Few years at most, it seemed to almost happen over night compared to the move from SSL to TLS for example.
SSH had been around for some five years or so before OpenSSH arrived. It slowly gained popularity on telnet/SSL and kerberized telnet because of the trivial small scale deployment, but also because it was a drop in replacement for rsh. Had it been fundamentally different it wouldn't have gone so easy, and I suspect the familiar language helped there.