Summary
What have we seen?
We can make very small, incremental improvements to the code. At each point, the latest version is better than the one before. We don't have to take the risk inherent in "Just scrap it and start over."
The unit tests act as a constant safety net. We never go more than a few minutes without the reassurance they provide.
Some improvements allow further improvements. The need for a Template class was far less obvious in the initial code.
Although it's possible that some refactorings may interfere with performance, they often will open up possibilities for dramatic improvements. Extracting the readTemplate() method allowed us to notice it was called for every substitution when it only needed to be called once; a future version of the Template class might be able to do all substitutions in one G pass. These possibilities are a much bigger factor than the "extra" procedure call that Extract Method originally introduced.
In a handful of moves (about 20), we've substantially improved our code.
Make refactoring (including testing!) a part of your normal programming practice. Sensitize yourself to code smells, and learn refactorings that can address them. It will pay off in the simplicity and flexibility your system will have.