8K should be lots of room.
even at 8Mhz, you have loads of time.
We have 'bots using ATMega8L's using Internal 1 Mhz clock and 5 line sensors with no issue.
1 MHz = 1million instructions per second.. even if you end up with a 1000th of that due to your code, that still means 1000 loops per second. 8 Mhz.. fah-get-about-it.
That is a ton of checking, and typically you'll end up making a decision and then ignoring input for about 50-100ms otherwise you end up overreacting to sensor input. (read: we usually have to dumb down the bot to make it react smoother)
A Google search of "Arduino based line follower" is recommended.
Also check and read through THIS site.
Consider joining a local robotics club such as the WCRS