I completely misunderstood what you were trying to do. Based on your problem description, I thought you were connecting to something via telnet and now wanted to connect via SSH. But what you're now describing is needing to SSH into one system and then from there telnet into a second system. That's a completely different scenario.
Now that I understand what it is you're trying to do, I agree with perlfan that creating an SSH tunnel is probably what you might want to consider. After you create the tunnel, your existing code using Net::Telnet just needs to connect to the local port of the SSH tunnel.