I see that you’ve solved it in another way, but if anyone wants to delete the Private prefix, this is how i did it:
In /wp-includes/post-template.php erase the folowing:
else if ( ‘private’ == $post->post_status ) $title = sprintf(__(‘Private: %s’), $title);