A mensagem de erro significa que o PuTTY não consegue nem conectar-se ao servidor ssh e apresentar a chave. Vale a pena verificar se você pode fazer o ping do host ao qual está tentando se conectar, e é por trás de um roteador que a porta necessária (geralmente 22) é encaminhada e que o servidor ssh está realmente em execução. Ou pode ser que você tenha sido bloqueado devido a muitas tentativas fracassadas, como Ryan disse, nesse caso tente de um computador diferente.
Você está na mesma rede que o servidor ou há roteadores intermediários?