A NET parece que só libera o uso de qualquer porta, como a porta 22 de ssh, para pessoa jurídica em seus novos planos (desde 2016).
Para conseguir usar o github por ssh com plano de internet da NET para pessoa física, é necessário:
Criar o arquivo ~/.ssh/config e adicionar:
Host github.com
Hostname ssh.github.com
Port 443
Conferir se funcionou:
ssh -T git@github.com
Hi username! You've successfully authenticated, but GitHub does not
provide shell access.
Confira o artigo completo em: https://help.github.com/articles/using-ssh-over-the-https-port/
Update: Parece que é na verdade um problema com o modem modelo TC7337NET da Technicolor. É possível resolver o problema também ligando para a Net e solicitanto assistência tecnica. O modem sendo trocado pelo Arris, resolveu segundo falaram nos comentários.
Obrigado, Guilherme
Deu certo!