Need Random Category Nav Menu

I don’t think you can use a menu for that, as menus are created manually in the Admin Panel.

You will have to use wp_list_categories like this:

$categories=get_categories();
$rand_keys = array_rand($categories, 5);
foreach ($rand_keys as $key) {
$cats .= $categories[$key]->term_id .',';
wp_list_categories('include=".$cats);