You can add a filter in the title like:
add_filter('the_title', function ($title) {
if (is_single()) {
$categories = get_the_category(get_the_ID());
// Assuming the post has many categories will take the first
$category = reset($categories);
return $category->name .' - '.$title;
}
return $title;
});