Why is my Exchange so slow

I am running Exchange 5.5 sp4. I have 60+ users in the home office, 15 regional offices= about another 45 employees. They connect to my mail server via a 56k frame relay (I know not the best option). Normally some of the users freeze up when theyreceive large attachements. Outlook will quit responding. Some offices have about 8 employees in them.

Why is it? Would it be a good idea to use 2 smtp protocols one handling incoming mail and one outgoing?

Any info is appreciated. Thanks,Paulo