Algumas coisas podem estar acontecendo aqui. Você pode encontrar a maioria das respostas no manual do seu shell, mas essas são geralmente incrivelmente longas e oblíquas, então ...
As chances são de que seu problema se resume a uma das poucas coisas.
Se o seu perfil ou o seu bashrc tiverem coisas caras, considere reduzi-los.
Se o seu perfil ou bashrc usar uma pesquisa reversa de DNS (para definir o prompt ou algo assim), corrija o DNS ou use o nome do host.
Os shells abrem muitos arquivos, entre outras coisas, durante a inicialização. Se a carga do sistema for alta, ela geralmente será exibida aqui.
Se o banner for pré-autenticação, também poderá ser autenticação (pam, LDAP, etc.) lenta.
Pode não ser nada disso, no entanto. Uma quantidade surpreendente de coisas acontece antes de exibir o prompt!