The problem was indeed my login script, although not to do with requiring a terminal (I’d suspected that and tested with the -t and -T options). The problem was that my .bashrc was running an exec (in this case to zsh – because our system doesn’t allow chsh to zsh).
The offending line:
test -f /usr/bin/zsh && exec /usr/bin/zsh
Solved by first checking for interactive shell and exiting if so:
[ -z "$PS1" ] && return
test -f /usr/bin/zsh && exec /usr/bin/zsh
So, essentially, because the shell was execing into zsh, ssh was waiting for this to finish – which never happened.
I am a little confused why my .bashrc was being called at all – I thought this was only for interactive shells, but the exact purpose and order of the various init scripts is something I don’t think I’ll ever learn.
I hope this can be useful to others who have some kind of exec in their startup scripts.
BTW – the other two answers were on the right track so I was completely unsure if I should ‘answer’ or just comment their answers. If answering my own question is morally wrong on stackoverflow, let me know and I’ll do penitence. Thank you to the other answerers.