Do I have to change web hosts if my host does not support DomainKeys at all?
No, you don’t have to necessarily. Instead, you can just switch DNS providers. Often your DNS records are hosted by the same people who host your site, but it does not have to be that way. Services like DNS Made Easy, ZoneEdit, easyDNS let you host just the DNS records with them, and keep all your sites elsewhere. This can be both faster and safer than hosting DNS and website together – it makes changing web hosts easier and also gives you more flexibility, so it is worth looking into.