Die Wärmeleistung, die der 7805 abgibt kannst mit dieser Formel annähernd berechnen:
(Eingangsspannung - Ausgangsspannung) * Ausgangsstrom

P = (Ue - Ua) x I

Wenn bei dir nur ein paar Milliwatt heraus kommen, dürfte sich der 7805 nicht nennenswert erwärmen. Hast du aber mehrere hundert Milliwatt oder kommst gar in den Watt-Bereich dann ist es kein Wunder, dass der Regler heiß wird. Dann brauchst du einen Kühlkörper. Oder du verringerst die Einggangsspannung (Ue) des Reglers. Unter 8 Volt solltest du aber dabei nicht gehen weil er dann nicht mehr richtig regelt.

Noch zu deiner Frage wegen der dubiosen 22µF ELKO's:
Hast du davon mehrere in deiner Schaltung und hängen Sie am Eingang vom 7805 oder am Ausgang? Am Ausgang vom 7805 solltest du anstelle des (oder der) ELKO's besser mehrere Keramikkondensatoren von 0,1 µF (=100 nF) verwenden, die du jeweils möglichst nah an den einzelnen IC's platzierst. Ein dicker ELKO gehört eher an den Eingang vom 7805 als an den Ausgang. Wenn du nämlich am Ausgang vom 7805 Kapazitäten mit insgesamt mehr als 10µF angeschlossen hast (was normalerweise unnötig ist) dann solltest du den Regler mit einer Diode schützen wie im Datenblatt http://cache.national.com/ds/LM/LM340.pdf auf Seite 11 oben rechts
angegeben. Ansonsten kann es passieren, dass sich diese Kondensatoren beim Ausschalten der ganzen Apparatur rückwärts durch den Regler hindurch entladen. Das könnte den Regler beschädigen. Vielleicht ist das bei dir bereits passiert.