Skewed Clustered Index
Primary Key and Clustered Index are really separate concepts and, although many tables put both of these attributes on the same constraint or index, this is not a requirement.

I do not see how changing the Clustered Index to the make it also the Primary Key will particularly help your performance.

It sounds like you have a Primary Key (BIGINT) already and that it is physically implemented through a unique non-clustered index.  This should be good for fairly quick lookups of the Primary Key since it would be a relatively narrow index.

As you have it defined now, the skewed Clustered Index is mostly the same special non-NULL value, with about 17.5K rows. 

Since you identify the Clustered Index as a likely pain point, you might look into whether a Filtered Index or an INDEXED VIEW would provide the needed performance improvement.

Sample of a Filtered View based on MSDN, like this:

CREATE NONCLUSTERED INDEX YourNonClusteredFilteredIndex
    ON dbo.YourTable (ClusterKeyCol)
    WHERE ClusterKeyCol IS NOT NULL; -- Or &lt;&gt; {special value}
GO


Sample of an Index View based on MSDN, something like this:

SET NUMERIC_ROUNDABORT OFF;
SET ANSI_PADDING, ANSI_WARNINGS, CONCAT_NULL_YIELDS_NULL, ARITHABORT,
    QUOTED_IDENTIFIER, ANSI_NULLS ON;
GO
CREATE VIEW dbo.YourClusteredView
WITH SCHEMABINDING
AS
    SELECT ClusterKeyCol, PrimaryKeyCol
    FROM dbo.YourTable
    WHERE PrimaryKeyCol &lt;&gt; {special value};
GO
--Create an index on the view.
CREATE UNIQUE CLUSTERED INDEX YourClusteredIndex 
    ON dbo.YourClusteredView (ClusterKeyCol);
GO


If you have a more detailed problem description, as John M asked, then perhaps some more targeted help can be provided.