It is not unusual for network equipment to have crappy SSH implementations and that seems to be the case you are currently facing.

You have two options

• Ask Cisco to fix the SSH server software in those routers (it would not be the first time I see that happening).
• Use Expect on top of Net::OpenSSH to talk to the router shell and run several commands in the same session.