The temple keys of Al Shedim
1. Saturas has one. Just ask him to give you the key.
2. Lester has one. You can get it by killing the Orcs near the temple. You may also beat Lester and take his key.
3, 4, 5. Three keys are hidden in chests in the ruins of Al Shedim - check the chests while exploring the area. .
The temple keys of Mora Sul
1. Kalesch - the Orc supervisor has one. When he attacks you beat him and take his key.
2. Kirk - the mercenary from Mora Sul has one. When he attacks you kill him and take the key.
3. Gonzales -the ruler of Mora Sul has one. He can sell the key for 10 000 gold coins. You may also kill him and take the key.
4. Yussuf - the slave has one. He can give you the key if you ask.
5. Ilja - the merchant has one. He can give you the key if you do him a favor.