It's a sort of regular occurrence that, after SSHing to a server (or even opening a terminal on my Mac), the login banner prints immediately but it takes ~10 seconds to a minute for the shell prompt to appear. After that, performance is fine and network latency is not unusual.
This doesn't seem like a computationally difficult, memory-intensive, or IO-heavy task. What's it doing with all those billions of CPU cycles?
ssh -v -v -vand
ur_shell -xmight be prudent debugging steps.