With ffmpeg, if you use -ss in input mode (ie before the -i), it looks for the nearest keyframe before but it doesn’t scan the full video so running it multiple time for each segment shouldn’t take much more time than a one pass software (and gives you the opportunity to do the segments in parallel if you can afford the I/O).