Ставим: aptitude install opendkim-tools

mkdir /etc/exim4/dkim

В конфиг /etc/exim4/exim4.conf.template пишем:

DKIM_DOMAIN = ${lc:${domain:$h_from:}}
DKIM_FILE = /etc/exim4/dkim/${lc:${domain:$h_from:}}.key
DKIM_PRIVATE_KEY = ${if exists{DKIM_FILE}{DKIM_FILE}{0}}
DKIM_SELECTOR = mail

это писать перед секцией:
remote_smtp:

или если конфиг разделен (при инсталле exim4 был вопрос "разделить конфиги на мелкие файлы?"), 
то писать в /etc/exim4/conf.d/transport/30_exim4-config_remote_smtp

Генерируем открытый и закрытый ключи для домена example.com:
opendkim-genkey -D /etc/exim4/dkim/ -d example.com -s mail

Эта команда создаст файлы etc/exim4/dkim/mail.private и/etc/exim4/dkim/mail.txt
с секретным и публичными ключами соответственно.

mail.private переименовать в example.com.key
например коммандами:
cd /etc/exim4/dkim/
mv mail.private example.com.key

то что в mail.txt - это прописывать в ДНС домена и можно удалять файл.
example.com.key так и оставлять где лежит.

И так для каждого домена. И потом рестарт екзима:
/etc/init.d/exim4 restart

Ну и проверяем через сервис http://www.mail-tester.com/ все ли у нас получилось