LM7805C alternative to produce less heat
If you can throw money at the problem, Murata has a switching regulator that is meant as a drop-in replacement for 7805.

Cost will be higher and ripple will be higher, but power loss will be much better.

The Murata part runs close to $10 in distribution. As Anindo points out in his comment, if you can afford a board layout change you can switching regulator modules with similar performance at considerably lower prices.