Something is definitely wrong. 
Direct Association should always be under 2 seconds, and usually faster than that.
Start by running a zwave repair utility and see if you get any error messages.
https://support.smartthings.com/hc/en-us/articles/200981864-How-do-I-make-sure-my-Z-Wave-devices-are-routing-optimally-
.
When you did the Association, did you use a minimote or?