You should try the "Smart cuts" feature (which is labelled experimental). On common formats/containers (like videos from YouTube) it works really well.
Basically it will attempt a precise cut and if it doesn't coincide with a keyframe it will reencode both ends on each side of the cut and the nearest keyframes.
It is generally very small segments to reencode so it is pretty quick and the quality of these is nearly lossless too so the cut feels invisible.
The only issue is if your segments are really short (under a second) it will generally fail... but chances are keyframe cuts in this case don't work well either.
Basically it will attempt a precise cut and if it doesn't coincide with a keyframe it will reencode both ends on each side of the cut and the nearest keyframes.
It is generally very small segments to reencode so it is pretty quick and the quality of these is nearly lossless too so the cut feels invisible.
The only issue is if your segments are really short (under a second) it will generally fail... but chances are keyframe cuts in this case don't work well either.