You never need a gate Key for killing a boss. If you see a boss under a Gate locked by a Key (not a blood) that will means that you have to take another way. Gate Key are just used for connect 2 areas between them and reduce the time you have to pass between these areas.
I believe Baby Witnesses are the yellow baby eye guys? They're under a Gate, i don't remember which, but I think it's on the way who link Mnemosyne's Forge to Eastern Shore.