8000 rpm can work. Are you using a cnc or manual mill, what are your maximum cutting speeds etc. FWIW I just milled a 6x8x2" block of 4130, takeing 3/4 of the material weight out. I used 7000 RPM 36 ipm, .04 stepover, and .05 depth of cut with a ball end mill. The finish pass was in the high speed spindle, 25k rpm, 1/4" ball end mill .01 step over, .01 depth of cut, 82ipm.. Both were cut dry with air blast, with OSG exo carb endmills.

More info is really needed on you setup to get you some better advise.