Se isso acontecer depois do carregamento do grub, é improvável que seja um problema de hardware, tanto quanto um problema de driver. Se os congelamentos estiverem causando corrupção, você pode usar algo como link para verificar e corrigir partições de inicialização.
Se for um problema de driver, eu recomendo usar o driver Radeon de código-fonte aberto NÃO o driver AMD Catalyst se você puder suportá-lo. link
Fora isso, a única forma real de testar falhas de placas gráficas é tentar o sistema com um cartão diferente e ver se o problema desaparece, mas se ocorrer de forma intermitente, pode não ser fácil verificar, a menos que você tenha outra placa gráfica. por aí.