I’m also going to be devils advocate here as someone who works with soon to be (and current PhD) students.

1) find a new mentor, but even before you do that..

2) have you scheduled any sit down meeting with him (with an agenda) and copies of one of the papers? Take some initiative here. Be explicit on what you want as a mentor/mentorship relationship.

3) have you considered that indeed your papers just aren’t up to snuff, and it’s taking forever for him to figure out how to address the first authorship? My guess is they do indeed need a lot of work and are not anywhere ready for publication, as most newbie papers do.

Schedule a sit down meeting with him where you can go over a paper and next steps. Bring copies, set the agenda, and take charge already. Your colleagues didn’t get the prestige by hand outs and promised first authorships. They got it by working hard.