Pode não ser uma solução perfeita, mas às vezes pode funcionar.
Apenas tente sftp://user@server em vez de ssh://user@server
Eu tenho vários marcadores nautilus apontando para servidores SSH, para que eu possa acessá-los facilmente. Do nada isso não funciona mais. Quando eu abro um marcador ou digito ssh://user@server na barra de localização, o Nautilus congela completamente e não recupera (edit: same com sftp: //). Eu posso matar o Nautilus e a área de trabalho será carregada novamente. Tudo mais funciona como deveria. Assim que eu tento acessar um servidor através do ssh, o nautilus congela novamente.
Nada foi alterado nos servidores e nenhuma atualização foi instalada no computador. Uma reinicialização também não ajuda.
Eu uso a autenticação de chave, se isso é importante. ESTOU sendo perguntado pela frase-chave e depois ocorre o congelamento.
Atualização: parou de funcionar enquanto eu estava usando. Eu estava fazendo upload de alguns arquivos, fiz outra coisa, e quando voltei para carregar alguns arquivos mais editados, o congelamento começou. Para mim isso parece com alguns arquivos de cache bagunçados ou incompletos que o nautilus ainda tenta usar.
Pode não ser uma solução perfeita, mas às vezes pode funcionar.
Apenas tente sftp://user@server em vez de ssh://user@server
Já tentou montar o sistema de arquivos remoto via sshfs e depois pesquisá-lo via Nautilus? Eu acho que se isso funcionar, então, eliminaria o servidor remoto, o cliente ssh local e partes não-gvfs do Nautilus como problemas. (Eu não tenho certeza do que está no meio ou se o gvfs está envolvido em tudo - mas ele forneceria mais informações se isso funcionasse.)