Clear[FastNextCarmichael]
FastNextCarmichael[n_] := 
      Module[{fertig = False, p = n}, 
While[
          Not[fertig], 
If[PrimeQ[p], 
            p = p + 1, 
factors = 
              Transpose[FactorInteger[p]]; 
If[
              Not[Union[
                      factors[[2]]] == {1}] || 
Not[
                  IntegerQ[(p - 1)/Apply[LCM, factors[[1]] - 1]]], 
              p = p + 1, 
              fertig = 
                True]]
]; 
p
]

(c = FastNextCarmichael[4]) // Timing

(c = FastNextCarmichael[c + 1]) // Timing

(c = FastNextCarmichael[c + 1]) // Timing

(c = FastNextCarmichael[c + 1]) // Timing