O pacote gzip tem prioridade, o que significa que deve sempre ser instalado para o sistema funcionar corretamente. Provavelmente, o aptitude está se recusando a removê-lo.
Btw: Remover o gzip é uma péssima ideia ...
Se você ver o gzip consumindo muita CPU, é porque algum outro programa está usando. Se você quiser fazer algo sobre isso, descubra qual programa está usando o gzip e altere o programa "se for possível". Para fazer isso, use pstree -apl
para ver todos os processos com seus pais, procure por gzip e seus pais, então verifique por que eles estão chamando para usar o gzip.