Для этого нужно отключить обращение к серверу DNS (аналог опции -d у tracert), после этого trace будет выполняться почти мгновенно:

router(config)#no ip domain-lookup

или

router(config)#no ip domain lookup