My Fedora box was responding slowly after DNS requests and I finally found that the fix is to disable parallel DNS requests. It appears that some firewalls have problems with parallel DNS requests (IPv6 and IPv4).
This means you need to add the following line to your /etc/resolv.conf
Or create the file /etc/NetworkManager/dispatcher.d/06-dhclientoptions with the following contents
#!/bin/bash echo "options single-request" >> /etc/resolv.conf