I don't really think this is related to hardware performance.
As a lover of Samurai Shodown series, I was used to play these games with an 8 years old machine.
Even without a video card they ran good (even with my older 15-years old machine).
Are you using x64 version of FBA? ...if yes, then, try the "standard" x32 version.
While someone else arrives here with some other suggestions, if you want, make a copy of your ".ini" settings, then delete the original one, run FBA and try to check video blitter settings.
First try to play with default ones and then Enhanced ones.
I remember, somewhere here, a friend posted a guide to recommended settings to use.
Try to search them, I'm pretty sure they are still around here... those settings are still valid and solid.