When did the Skutatoi come around?

[Praefectusclassis]

Scutati in fact occur in the early empire as well, e.g.:
Belegstelle: AE 1906, 00035
Provinz: Africa proconsularis Ort: Choud el Batel
[L]ongeio Q(uinti) Longei Festi f(ilio) Quirina Ka/[3]o equo publico adlecto praefecto co/[hort]is Scutatae civium Romanorum Alexandriae / [3]ea Q(uinti) Peducaei Spei f(ilia) Sextia mater eius flaminica perpe/[tua K]arthaginiensium pio optimo sanctissimo dignissimo / filio fecit