Há um recurso ativado por padrão que tenta procurar pacotes desinstalados que possam fornecer o comando digitado. Isso deve ser muito rápido, mas parece que por algum motivo no seu sistema, não é.
Existem várias coisas que você pode fazer para diagnosticar isso, mas para resolver o problema imediato, é possível desativar esse recurso com
sudo dnf remove PackageKit-command-not-found