Using a 5KVA step-down toroid transformer as a step-up transformer

You are correct. The transformer will only reduce the voltage (and increase the available current), so you need to add additional circuitry to rectify, smooth and regulate your 12\$V_{AC}\$ transformer output to 5\$V_{DC}\$.

This is the type of circuit you should be looking to build:

1. The transformer reduces the voltage from mains to 12\$V_{AC}\$ (RMS).
2. The Diode Bridge (known as a bridge rectifier) will convert 12\$V_{AC}\$ to 15\$V_{DC}\$. The voltage is \$\sqrt{2}\$ times minus two diode voltage drops higher than the input voltage because the rectifier output is the peak AC voltage, not the RMS AC voltage.
3. The first capacitor will smooth out the ripples that come from the output of the AC to DC bridge rectifier.
4. The LM7805 regulator will maintain a constant voltage as the load varies. For example if you are switching a light bulb on and off, the current will go up and down, and if you didn't have a regulator then the voltage would drop as the bulb is switched on. The regulator keeps it at the 5\$V_{DC}\$ your microcontroller needs.
5. The final small capacitor filters out any noise or interference on the regulated side of the circuit.

The below assumes you are using the correct term 'transformer' for a heavy mostly metal device that outputs 12VAC from mains voltage. If you actually have a switching wall wart adapter that outputs 12VDC then you can omit the bridge rectifier and large filter capacitors shown below, but the solutions are otherwise the same.

Your transformer will give you 12VAC (RMS) - actually probably more like 14V with a light load. If you add a bridge rectifier and capacitor you'll get approaching 20VDC with no load and more like 14VDC with a heavier load. One approach is to simply use a linear regulator such as an LM7805 to reduce the voltage to 5V. The main issue with that is that it's going to waste 2/3 of the power and get very hot with a 750mA load (and thus will require a large heatsink to not destroy itself).

Another approach would be to buy a module that uses an LM2596 regulator (or build a circuit using that regulator). There are such modules available cheaply from China (eg. eBay)n, though I believe the 'LM2596' is typically a counterfeit.

The schematic would look something like this:

Though you'd probably want to increase C1 to 2200uF/25V or more.

If you buy a module the parts after the bridge rectifier and C1 are in the module. You can also buy kit power supplies that are missing all but the transformer.

The LM7805 circuit would be more like the below (again with C1 increased to more like 2200 or 3300uF/25V).

The LM7805 will need a heatsink maybe 100mm x 100mm 3mm thick aluminum plate or thereabouts.

As is well explained elsewhere on this site (Olin has written a canonical answer) the voltage rating must match your device, but the current rating needs to be the same or higher than your requirement. At 5V 10A power supply will not force 10A through your device if it is designed to draw 750mA at 5V. A 5V 1A supply will also work, but not a 5V 0.5A supply.

The super-easy solution (and this is not a design thing) is to just buy a switching wall plug adapter that outputs 0.75A or more at 5.0V. For example, an Ethernet router power supply that outputs 5V@2A would work just fine. They're cheap and good enough for many purposes (and generally safety-agency approved so you won't likely get a shock from the mains).