I have used Custom Select Query to gather all information in a single call and hope it may work out.
global $wpdb;
$selected_cat_id = '6,7,8,9';
$post_count = 5;
$custom_query = "SELECT $wpdb->posts.ID, $wpdb->posts.post_title, $wpdb->terms.name FROM $wpdb->posts
LEFT JOIN $wpdb->term_relationships ON ($wpdb->posts.ID = $wpdb->term_relationships.object_id)
LEFT JOIN $wpdb->terms ON ($wpdb->term_relationships.term_taxonomy_id = $wpdb->terms.term_id)
WHERE 1=1 AND ($wpdb->term_relationships.term_taxonomy_id IN ($selected_cat_id))
AND $wpdb->posts.post_type="post" AND ($wpdb->posts.post_status="publish" OR $wpdb->posts.post_status="private") ORDER BY $wpdb->posts.post_date ASC";
$pageposts = $wpdb->get_results($custom_query, OBJECT);
$cat_posts = array();
foreach($pageposts as $post){
$cat_posts[$post->name][$post->ID] = $post->post_title;
}
foreach($cat_posts as $key => $values) {
$category_id = get_cat_ID( $key );
echo '<a href="'.get_category_link($category_id).'">'.$key.'</a>';
$values = array_slice($values,0,$post_count,true);
echo '<ul>';
foreach ($values as $post_id => $value){
echo '<li><a href="'.get_permalink($post_id).'">' . $value . '</a></li>';
}
echo '</ul>';
}