Insta-Name... Just Add Coder!

JavaScript ES6, 187 180 168 bytes

f=l=>{r=m=>Math.random()*m|0
d=l%2&&r(--l/2)*2+1
for(s='';l--;s+=s?a:a.toUpperCase())a=l%2?'bcdfghjklmnpqrstvwxyz'[r(21)]:'aeiou'[r(5)]+(l==d-1?'hy'[r(2)]:'')
return s}

Edit: I switched from using regex replace to a simple for loop, which improved the length considerably. Ungolfed code and test UI below. Input a negative number at your own risk because it makes an infinite loop. (Thanks to unclemeat for pointing that out.)

f=function(l){
  // Function to return a random integer between 0 and m-1 inclusive
  r=function(m){
    return Math.random()*m|0
  }
  // d is the position the h or y will be added
  // l is decremented only if l is odd so an extra consonant won't be added to the end
  d=l%2&&r(--l/2)*2+1
  
  for(s='';l--;){
    a=l%2?'bcdfghjklmnpqrstvwxyz'[r(21)]:'aeiou'[r(5)]+(l==d-1?'hy'[r(2)]:'')
    // If `s` is empty (i.e. this is the first leter), make it uppercase
    s+=s?a:a.toUpperCase()
  }
  return s
}

run=function(){ip=parseInt(document.getElementById('input').value);if(ip<2)return alert('Input must be greater than one.');document.getElementById('output').innerHTML=f(ip)};document.getElementById('run').onclick=run;run()

<input type="number" id="input" value="7" min="2" /><button id="run">Run</button><br />
<pre id="output"></pre>

Pyth, 33 bytes

rsXOtQmO*-GJ"aeiou"J/Q2*%Q2O"hy"4

Demonstration.

SWI-Prolog, 286 285 bytes

a(I):-a(I,[]).
a(I,R):-(I=1,r(1,K),nth0(K,`hy`,V),length(R,L),random(1,L,W),nth0(W,[O:P|Q],V:0xFEFF,R);I=0,[O:P|Q]=R),N is O-32,p([N:P|Q]);r(5,A),nth0(A,`aeiou`,X),r(21,B),nth0(B,`bcdfghjklmnpqrstvwxyz`,Y),J is I-2,a(J,[Y:X|R]).
p([A:B|R]):-put(A),put(B),p(R);!.
r(I,R):-random(0,I,R).

Example: a(13). outputs Leqihsekeqira.

Note: You might need to replace the ` with " if you have an old version of SWI-Prolog.