Agree with zador. What you can try to do (if possible) is lower the voltage to 8-9V, instead of 12V. That will remove 1W of heat from the 7805. Also install a heatsink on the regulator, and do not forget to add a electrolytic capacitor of 220uF - 1000uF at the output of the regulator to take care of the current surges a SBC produces at times.
Depending on the exact type of the 7805 you might run into the max. current handling capacity. The most common TO220 version is standard 1A max... There are 78M05 units, but those will require a heatsink for the much higher current.
All in all is a 7805 a poor choice for your application. I would recommend looking at a switching regulator of i.e. Recom. Do not forget the additional capacitance on the output though...
For the 78xx electrolytic cap should be on input and ceramic cap should be on output (as close to the regulator as possible). For all types of regulators looking at the datasheet is recommended before trying to apply a common sense - some require a ceramic cap on the output while others require electrolytic one for the stability.
In any case 78xx or any kind of linear regulator should not be used here - it will consume more power than the board itself at this voltage difference.