Po prečítaní dokumentácie to vyzerá tak, že prvý parameter KeyFrame je čas, v ktorom má daná zmena nastať (pôvodne som myslel, že je to doba trvania frame-u). Takže ju treba vypočítať podľa indexu, asi takto:

IntStream.range(0, COLORS.length)
        .mapToObj(index -> new KeyFrame(Duration.millis(index * 400), event -> { rectangle.setFill(COLORS[index]); }))
        .forEach(timeline.getKeyFrames()::add);

Ak má byť farebný prechod plynulý, tak by som si pozrel dokumentáciu k FillTransition.