How to speedUp Random selecting in SQlserver

I Have a table for phone Number such as this : ID PhoneNumber Enabled isUsed CountryID

---

10444 ***001000999 1 NULL 1 10445 ***001000998 1 NULL 1 10446 ***001000994 1 NULL 1 10447 ***001000990 1 NULL 1 10448 ***001000989 1 NULL 1

this table have 68992507 record !! I want to select some Random phone number from it .

I can get My Random number Query by this SP :

here i select random numbers , insert to a @table and then update the selected numbers .

CREATE proc [dbo].[Mysp_GetRandom]
@countryid int,
@count int
as
declare @tbl table(
[ID] [int] ,
[PhoneNumber] [nchar](20) NOT NULL,
[Enabled] [bit] NULL,
[GrupID] [tinyint] NULL,
[CountryID] [int] NULL)


insert into @tbl
SELECT top(@count) *
FROM tblPhoneNumber
WHERE CountryID = @countryid and GrupID is null
order by binary_checksum(ID * rand())
Update tblPhoneNumber set GrupID = 1 where ID in (select ID from @tbl)
select * from @tbl

The Problem is Loooongn Time for get Query !! for Example this query get 12:30 minuts !!! :

GO

DECLARE @return_value int

EXEC    @return_value = [dbo].[Mysp_GetRandom]
    @countryid = 14,
    @count = 3

SELECT  'Return Value' = @return_value

GO

and I set Index on this table :

CREATE NONCLUSTERED INDEX [NonClusteredIndex-20150415-172433] ON [dbo].[tblPhoneNumber]
(
    [CountryID] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
GO

also see this screen shot : enter link description here

thanks ...