I use Splines too and what I do is using the first derivation to calculate the spline direction of movement on the spline and move the agent along this normal.

You do not have to do exacly that, but what you definatly need is a method to find the current positon of the agent along the spline. This Method works fine for me and it is really fast too.
Do not iterate over the whole spline every frame!