Due to my expirience- call set up time is very dependent of NSS part, but not from BSS.
Last time, when I had this problem – there was a problem on core signalling(c7) network.
So, pay your attention to signalling links between BSC and MSC (A-int). Due to vendors recommendation- it shouln’t be more than 40% per link.