Huh! Thanks guys, I hadn't even considered the different SSH ciphers/versions, that does seem to have eased the connection problems
And I'll definitely have to give the commercial client a shot! As much as I'm connected from my phone, would probably be worthwhile to use the best out there.