The official arduino uno schematic uses a NPC1117 voltage regulator. This is a linear one. This means that if you put 12V on it, and if your system requises 0.5A, you Will leak 0.5A on the 12V, and, if there is 5V on the output, 12V on the input, there is a 7V drop on the regulator, 7V * 0.5A = 3.5W that turns into heat.
To avoid overheating, the solution isn't to increase the input voltage, but to decrease it. If you have a 6.2V power supply, this will minimize overheating. At least 6.2V are required for the NPC1117 to provide a stable 5V.
An other option is to use a USB 5V power supply with an output current greater than 0.5A. This is often used with smartphones. This allows to bypass the NPC1117, but the power supply shall be exactly 5V (where exactly stands for less than 10% of over or undervoltage).
Also, please note:
Arduino does not recommend bypass[ing the] Vin supply to directly supply 5V rail on the board as it will damage the NPC1117. See the first two line on page # 3 from the document link below. http://media.digikey.com/pdf/Data%20Sheets/Arduino%20PDFs/ArduinoEthernet.pdf
You can either do the soldering and remove NPC1117 chip before you apply 5V directly onto the board or find a higher current capability power supply with the output voltage between 7v-12V.