Clear[NextCarmichael]
NextCarmichael[n_] := 
      Module[{fertig = False, p = n, a}, 
While[
          Not[fertig], 
If[
            Not[PrimeQ[p]], 
liste = 
              Table[PowerMod[a, p, p] - a, {a, 
                  p - 1}]; 
liste = 
              Union[liste]; 
If[liste == {0}, 
              fertig = True, p = p + 1], 
            p = p + 1]]; 
p]

(c = NextCarmichael[4]) // Timing

FactorInteger[c]

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

FactorInteger[c]

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

FactorInteger[c]

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

FactorInteger[c]

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

FactorInteger[c]