Die Regex ist sicher optimierbar:

Wenn der ersten Teil matched und der zweite nicht, wird über jede mögliche Länge von .* gebacktrackt.
Wenn du keine HTML-Tags in (.*?) zulassen willst, macht [^<]* das ganze sehr viel effizienter.

Wenn doch... schwierig. Du könntest probieren mit (?>...) was zu reissen, aber das hängt davon ab, was du genau erlauben willst.

Die andere Frage ist: Hast du deinen Code mal durch einen Profiler gejagt, um zu schauen, ob diese Funktion wirklich das ist, was viel Zeit frisst?
Und was spricht gegen ein "fertiges" Templating-System wie HTML::Template::Compiled, HTML::Template oder Template?