I think that your best bet would be to do a minor re-design of your application at this point. Rather than sending an email directly, you should be writing a job to a queue (eg by writing to a table in a database). Another job should then run in the background to process that queue (eg from cron) and actually send the messages. This is much more resiliant in case of downtime (eg mailserver maintenance won't take your site down), and won't force your users to wait whilst your application tries to send mail.

If you don't want to do that though, then the first thing I'd check is whether you're talking to a remote mailserver, or one that's running on the local machine. Talking to a mailserver on the local machine is likely to be a lot faster than talking to a remote machine.

If that isn't the problem, and you're running sendmail locally, then stopping sendmail trying to do ident queries may also help (confTO_IDENT in your sendmail.mc file), as may checking your /etc/hosts file to make sure you have a proper entry for localhost in there.