If you don't know what's slow, profile it. Just the other day tim.bunce released Devel::NYTProf 2, which also has a good interface for profiling web applications.

If the database is the bottleneck, see if you can add some indexes on relevant columns.

If the template is the bottleneck, use HTML::Template::Compiled, which is a (nearly) drop-in replacement for HTML::Template, but which compiles the templates and caches the compiled form, if set up appropriately.