Deleted Page doesn't delete item from Nav Menu


In my theme, I have the following code in header.php to display my top nav menu:

<?php wp_nav_menu(array('theme_location'=>'primary','menu_id'=>'suckerfishnav','container'=>'div','container_class' => '','menu_class'=> 'suckerfishnav'));?>

Under Appearance -> Menus, I have a nav menu named “Main menu” which is assigned to the Main Menu. The issue is when I delete a page under the “Pages” section, the Main menu still shows that item on my site which if I click it, it generates a 404 error.

How can I have the menu remove an item once that page is put in trash?