The max number of fields that will be in the file will be 23, so what seems to work is this:
sort -t ':' -k1,1 -k2,2 -k3,3 -k4,4 -k5,5 -k6,6 -k7,7 -k8,8 -k9,9 -k10,10 -k11,11 -k12,12 -k13,13 -k14,14 -k15,15 -k16,16 -k17,17 -k18,18 -k19,19 -k20,20 -k21,21 -k22,22 -k23,23 -o <newfile> <oldfile>...