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

options single-request

Or create the file /etc/NetworkManager/dispatcher.d/06-dhclientoptions with the following contents

#!/bin/bash

echo "options single-request" >> /etc/resolv.conf