Retina 0.8.2, 85 bytes

T`_o`A\EIOUA-DF-HJ-NP-TV-ZBaei\oua-df-hj-np-tv-zb
i`[b-z-[eiou]](?=[b-z-[eiou]])
$&ei

Try it online! Link includes test cases. Edit: Fixed the character classes so that digits were not counted as consonants. (Character class subtractions allowed me to avoid increasing the byte count.) Explanation:

T`_o`A\EIOUA-DF-HJ-NP-TV-ZBaei\oua-df-hj-np-tv-zb

Translate each letter in the string to the next letter in the string. E and o are special so have to be quoted in the replacement string (o in the source string refers to a copy of the replacement string) while - indicates a character range (also avoids having to quote H and h). _ in the source string is just a filler to align the strings.

i`[b-z-[eiou]](?=[b-z-[eiou]])
$&ei

Case-insensitively find pairs of consecutive consonants and insert ei after the first.

C (clang), 152 149 bytes

-3 bytes thanks to ceilingcat!!

*i,c,u,p;z(s){i=wcschr(s,c-u);c=i?i[1]:c;}f(*s){for(p=0;c=*s++;p=i)u=c/91*32,z(L"AEIOUA"),z(L"BCDFGHJKLMNPQRSTVWXYZB"),printf("ei%c"+(!p|!i)*2,c+u);}

Try it online!

05AB1E, 28 26 bytes

žNÃü2D€S„aeý:žNžM‚Du«vyDÀ‡

Try it online.

ü2D€S could alternatively be SãDJs: try it online.

Explanation:

žN             # Push the consonants constant
  Ã            # Only keep those characters from the (implicit) input-string
   ü2          # Pop and push its overlapping pairs as strings
     D         # Duplicate this list of string-pairs
      €S       # Convert each 2-letter string to a character-pair
        „aeý   # Join each pair with "ae" delimiter
            :  # Replace all pairs with the 4-letter strings in the (implicit) input
žN             # Push the consonants constant
  žM           # Push the vowels constant
    ‚          # Pair them together
     Du«       # Merge an uppercase copy of this pair
        vy     # Loop over all four strings:
          D    #  Duplicate the current string
           À   #  Rotate its copy once towards the left
            ‡  #  Transliterate the characters in the input-string
               # (after which the result is output implicitly)

   S           # Convert it to a list of characters
    ã          # Create all possible character-pairs with the cartesian power of 2
     D         # Duplicate this list of character-pairs
      J        # Join each inner character-pair to a 2-letter string
       s       # Swap so the character-pair list is at the top of the stack again

Goruby -p, 99 bytes

c="aeiou"+b="bcdfghj-np-tv-z"
d="eioua"+b[1..]+?b
$_.t!c+c.up,d+d.up
gsub(/[#{b}]{2}/i){_1.t.j"ei"}

Attempt This Online!

Ruby, 110 bytes

c="aeiou"+b="bcdfghj-np-tv-z"
d="eioua"+b[1..]+?b
$_.tr!c+c.upcase,d+d.upcase
gsub /#{"([#{b}])"*2}/i,'\1ei\2'

Attempt This Online!

JavaScript (Node.js), 131 bytes

s=>s.replace(/[a-z]/gi,c=>(s+g(i=B(c)[0]-1)?"":"ei")+(h=j=>g(i)^g(j=-~j%26)?h(j):B([j+1|i&96]))(i&31),B=Buffer,g=i=>s=1065233>>i&1)

Try it online!

Commented

s => s.replace(    // replace in the input string s ...
  /[a-z]/gi, c =>  //   ... each letter c (case insensitive)
  (                //
    s +            //   if the previous letter was a vowel (or this
                   //   is the 1st iteration and s is still a string)
    g(             //   or the current letter
      i =          //     whose ASCII code - 1 is loaded in i
      B(c)[0] - 1  // 
    ) ?            //   is a vowel:
      ""           //     append nothing
    :              //   else:
      "ei"         //     append "ei"
  ) + (            //
    h = j =>       //   h is a recursive function looking for the
                   //   replacement letter
    g(i) ^         //     if the type of the current letter
    g(             //     does not match the type of
      j = -~j % 26 //       the next letter in the alphabet
                   //       obtained by incrementing j modulo 26
    ) ?            //     then:
      h(j)         //       keep advancing by doing a recursive call
    :              //     else:
      B([          //       output the letter
        j + 1 |    //         whose ASCII code is j + 1
        i & 96     //         with bits #5 and #6 taken from i
      ])           //
  )(i & 31),       //   initial call to h with j = i mod 32
  B = Buffer,      //   define B for Buffer
  g = i =>         //   g is a helper function taking an integer
    s = 1065233    //   representing an ASCII code minus 1,
        >> i & 1   //   returning 0 for consonant / 1 for vowel,
                   //   and also saving the result in s
)                  // end of replace()

Charcoal, 57 bytes

≔⪪aeiou¹θ≔⁻⪪β¹θη⊞υ⁰⭆Ｓ⁺×ei×⊟υΣ⊞Ｏυ№η↧ι⊟ＥΦ⟦ιθη↥θ↥η⟧№λι§λ⊕⌕λι

Try it online! Link is to verbose version of code. Explanation:

≔⪪aeiou¹θ

Get a list of the vowels in lowercase.

≔⁻⪪β¹θη

Subtract them from the lowercase alphabet to leave the consonants.s

⊞υ⁰

Start off with no previous consonant.

⭆Ｓ⁺

Map over each input character, joining together...

×ei×⊟υΣ⊞Ｏυ№η↧ι

... "ei" repeated the number of times the previous character was a consonant times the number of times the current character is a consonant, saving the result for the next iteration, ...

⊟ＥΦ⟦ιθη↥θ↥η⟧№λι§λ⊕⌕λι

... taking any of the uppercase consonants, uppercase vowels, lowercase consonants or lowercase vowels that contain the character, or as a last resort the original character, cyclically rotating the character in that list.

Vyxal, 27 bytes

k⁰kv":ɾJJƒ*‛ß+k⁰⇧1Ṁ$‡‛eijøṙ

Try it Online!

This is a bit of a mess.

k⁰kv"                       # Consonants and vowels, paired
     :ɾ                     # Duplicate and make an uppercase copy of each
       J                    # Concatenate to the original
        J                   # Concatenate to the input
         ƒ*                 # Reduce by ring translation, ring translating by each string
           ‛ß+              # "[bcdfghjklmnpqrstvwxyz]+"
                 1Ṁ         # Insert at position 1...
              k⁰⇧           # "BCDFGHJKLMNPQRSTVWXYZ"
                   $        # Put that under the value
                         øṙ # Regex replace that with...
                    ‡       # A function that...
                     ‛eij   # Joins by "ei"

Python, 166 bytes

f=lambda s,v='UOIEA',c='BZYXWVTSRQPNMLKJHGFDC':s and[y:=(q:=[x:=(t:=s.upper())[0],[v,c][x in c]][x in v+c])[~-q.find(x)],y.lower()][y<s]+'ei'*({*t[:2]}<{*c})+f(s[1:])

Attempt This Online!

sed -E, 131 bytes

s/[A-Z]/@\l&/g
y/bcdfghjklmnpqrstvwxyzaeiou/cdfghjklmnpqrstvwxyzbeioua/
:a
s/@(.)/\u\1/
s/[b-df-hj-np-tv-z]{2}/!&/i
s/!(.)/\1ei/
ta

Attempt This Online!

This code expect that there won't be characters @ and ! input. Any two characters could be used instead of those, I think that even unprintable ones should work (at least using escape codes), but I chose to keep it as is to make it readable. Also this program could be made without this restriction, but it would be longer and less interesting.

Explanation:

s/[A-Z]/@\l&/g              # lowercase all characters and make note which characters were lowercased
                              # this have to be done because transliteration (following command) is case sensitive
                              # otherwise there would have to also be all uppercase characters
y/bcdfghjklmnpqrstvwxyzaeiou/cdfghjklmnpqrstvwxyzbeioua/ # change character to next one
:a                          # beginning of loop
s/@(.)/\u\1/                # uppercase back all characters where we made note
                              # it is inside of loop, to save 1B by not using g flag
s/[b-df-hj-np-tv-z]{2}/!&/i # make note where to place string ei
                              # this is done so that the long bracket expression doesn't need to be repeated twice
                              # also this command is the reason for loop as sed doesn't supported overlapping replacements
s/!(.)/\1ei/                # put ei after noted character
ta                          # repeat till there is nothing to replace