O motivo é tão lento porque ele está executando uma compilação completa da política quando você executa o comando. (Veja este BZ: link , Dan Walsh é um dos mantenedores da política do SELinux no RHEL e no Fedora ). Ele foi corrigido em versões posteriores do Fedora, o que significa que ele provavelmente acabará corrigido no EL7 e possivelmente em versões posteriores do EL6.